Problem Set 4 latex source
This file is provided to help students create their solutions
in latex if they wish. Some formatting was removed for clarity.
It is missing some macros, but you can figure out what they are
by looking at the pdf image. It is not a working latex file.
\item[0.1] Read and solve, \underline{but do not turn in}: \ Book, 7.6
\ [P is closed under $\cup, \concat,$ and complement] \\
Review the proof that P is closed under *, covered in recitation.
(See Book, 7.15)
\item[0.2] Read and solve, \underline{but do not turn in}: \
NP is closed under $\cup, \concat,\, \cap,$ and *.
\item
Let $\lang{MODEXP}=\setb{ a,b,c,p } a,b,c,p$ are positive
binary integers such that $a^b \equiv c \! \pmod{p}\setend$. \\
Show that $\lang{MODEXP} \in $ P. (You can assume that basic
arithmetical operations, such as $+$, $\times$, and mod, are
computable in polynomial time.)
\item
Let $\lang{UNARY-SSUM}$ be the subset sum problem in which all
numbers are represented in unary, i.e., $\st1^k$ represents the number
$k$. Why does the \np-completeness proof for \subsum\ (see textbook)
fail to show $\lang{UNARY-SSUM}$ is \np-complete?
Show that $\lang{UNARY-SSUM}\in \poly$.
\item
Show that if $\poly = \np$, then every language $A \in \poly$,
except $A=\emptyset$ and $A=\Sigma\kstar$, is \np{-}complete.
\item
Show that if $\poly = \np$, we can factor integers in polynomial time. \\
(Note: The algorithm you are asked to provide computes a function,
and NP contains languages, not functions. Therefore, you cannot solve
this problem simply by saying ``factoring is in NP and P $=$ NP so
factoring is in P''. The assumption $\poly = \np$ implies that
all \emph{languages} in NP are in P, so you need to find an NP language
that relates to the factoring function.)
\item
Let $\lang{CNF}_k = \setb{\phi} \phi$ is a satisfiable cnf-formula
where each variable appears at most $k$ times\setend.
Show that $\lang{CNF}_2 \in \poly$.
\item
Define $\lang{CNF}_k$ as above.
Show that $\lang{CNF}_3$ is NP-complete.
\item[$7.^{\!\star}$] (optional)
The \defin{difference hierarchy} $\dps{i}$ is defined recursively as
\begin{enumerate}
\item[i.] $\dps{1} = \np$, and
\item[ii.] $\dps{i} = \set{ A} A = B \setminus C
\text{ for $B$ in \np\ and $C$ in $\dps{i-1}$}\setend$.
(Here $ B \setminus C = B \inter \overline{ C}$.)
\end{enumerate}
For example, a language in $\dps2$ is the difference of two \np\ languages.
Let $\dpp = \dps{2}$.
Let
$$Z=\setb{ G_1,k_1, G_2,k_2} G_1 \text{ has a $k_1$-clique and $G_2$
doesn't have a $k_2$-clique\setend.}
$$
\begin{parts}
\item Show that $Z$ is complete for \dpp.
In other words, show that $Z$ is in \dpp\ and
every language in \dpp\ is polynomial time reducible to $Z$.
\item Let $\lang{MAX-CLIQUE} = \setb{ G,k}$a largest clique in
$G$ is of size exactly $k$\setend. \\
Use part (a) to show that $\lang{MAX-CLIQUE}$ is \dpp-complete.
\end{parts}