\documentclass{article}

\input{6045preamble}

\begin{document}

\homework{8}{Prof. Ron Rivest}{Due: 7 May 2003}{Your Name Here}

\begin{problem}
Consider the following problem:
Given a multivariate polynomial, $P(x_1, x_2, \ldots, x_n)$, determine 
whether the polynomial is uniformly zero when its inputs are restricted to 
be either 0 or 1.

Argue that a polynomial time algorithm that solves this problem is unlikely
to exist.
\end{problem}


\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}

\begin{problem}
Consider the problem:
\begin{eqnarray*}
HALF-SAT = \{ \phi &|& \phi \mbox{is a Boolean formula that is}  \\
                   & & \mbox{satisfied by exactly half of the possible} \\
                   & & \mbox{assignments of truth values to its variables} \}
\end{eqnarray*}    
Argue that HALF-SAT is unlikely to solvable in polynomial-time.

\textbf{Hint:} First argue that UNSAT is unlikely to solvable in polynomial time, where
UNSAT is the set of boolean formulas such that no assignment of truth values to 
variables makes the formula true.
\end{problem}


\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution}

\begin{problem}
Prove that the following problem is NP-Complete:
\begin{eqnarray*}
NA = \{<M,x> &|& \mbox{M is a non-deterministic TM that accepts} \\
             & & x \mbox{ in at most } |x|^2 \mbox{ time steps} \} 
\end{eqnarray*}

\textbf{Hint:} Consider how running time is affected by adding zeros to the 
front of an algorithm's input (For correctness, the algorithm should
be modified to ignore leading zeroes).
\end{problem}


\begin{solution}
%
%
%
  Your solution goes here. 

%
%
%
\end{solution} 

\end{document}