\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor}
\usepackage{varwidth,multicol}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\st}{~\mid~}
\newcommand{\blank}{\textvisiblespace}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}
\name{}
\class{CSE 105}
\assignment{Individual Homework 8}
\duedate{Not to be turned in; Solutions will be posted on Piazza on Friday 3/16 }
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
This {\bf Individual HW8} covers the material from Chapter 7 you should
be be comfortable with. You can use it to help you study for the final exam. \\
{\sc Reading} Sipser Highlights from Chapter 7.
\newline
{\sc Key Concepts} Running time of a Turing machine, time complexity classes,
polynomial time ($P$), proving that a problem is in $P$, $NP$, proving
that a problem is in $NP$, polynomial-time reduction, $NP$-completeness,
examples of $NP$-complete problems, using reduction to prove $NP$-completeness
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.]
\begin{enumerate}
\item[a.]
Prove that $P$ is closed under complementation.
\item[b.]
It is not currently known whether $NP$ is closed under complementation.
Would knowing that (i) $NP$ is closed under complementation
or that (ii) $NP$ is not closed under complementation
give us any information about whether $P = NP$? Briefly justify your answer.
\end{enumerate}
\end{problem}
\begin{problem}[2.]
Let $n$ be the number of states in a DFA. Show that $E_{DFA} \in P$
by showing that the algorithm in the proof of Theorem 4.4 (that $E_{DFA}$ is a
decidable language) runs in polynomial time (as a function of $n$).
\end{problem}
\begin{problem}[3.]
In class (on Wed, March 14, Pi day) we gave a polynomial-time reduction from 3SAT to CLIQUE.
You can also find the details on page 302 of the textbook.
Apply this reduction to the formula
\[
\phi = (x_1 \vee x_2 \vee x_3) \wedge
(\overline{x_1} \vee \overline{x_2} \vee\overline{x_3} )
\wedge
(x_1 \vee \overline{x_2} \vee \overline{x_2} )
\wedge
(\overline{x_2} \vee \overline{x_3} \vee x_3)
\]
with $4$ clauses.
(We are using the book's convention that $\overline x$ means $\neg x$).
Is the formula satisfiable? Does the graph have a $4$-clique?
{\it Hint: the answers to these questions should {\it both} be yes or {\it both} be no.}
\end{problem}
\end{document}