%
% To use this as a template for turning in your solutions, change the flag
% \inclsolns from 0 to 1. Make sure you include macros.tex in the directory
% containing this file. Edit the "author" and "collaborators" fields as
% appropriate. Write your solutions where indicated.
%

\def\inclsolns{0}
\documentclass[12pt]{article}

\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{enumitem}
\usepackage{comment}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{hyperref}

\input{macros}

\theoremstyle{definition}

\ifnum\inclsolns=1
\newenvironment{solution}{\paragraph{Solution.}}{}
\else
\newenvironment{solution}{}{}
\excludecomment{solution}
\fi


\makeatletter
\def\collaborators#1{\gdef\@collaborators{#1}}
\def\@collaborators{\@latex@warning@no@line{No \noexpand\collaborators given}}
\makeatother

\author{Ada Lovelace}
\collaborators{Charlie Babbage, Mike Faraday}

\begin{document}


\begin{center}
{\Large CS 535: Complexity Theory, Fall 2023}

\bigskip

{\Large Homework 3}

\smallskip

Due: 11:59PM, Tuesday, September 26, 2023.

\end{center}

\ifnum\inclsolns=1
	\makeatletter
	\noindent Name: \@author \\
	Collaborators: \@collaborators
	\makeatother
\else
\fi

\paragraph{Reminder.}
Homework must be typeset with \LaTeX\ preferred. Make sure you understand the course collaboration and honesty policy before beginning this assignment. Collaboration is permitted, but you must write the solutions {\em by
	yourself without assistance}. You must also identify your
collaborators. Assignments missing a collaboration statement will not be accepted. Getting solutions from outside sources such as the
Web or students not enrolled in the class is strictly forbidden.

\bigskip


\begin{problem}[Decision vs. Optimization]
	An $\NP$ minimization problem is specified by a polynomial-time computable \emph{objective function} $f : \{0, 1\}^* \times \{0, 1\}^* \to \N$ and a polynomial $p$. Given an input $x \in \zo^*$, the problem is to find a $y \in \zo^{p(|x|)}$ that minimizes $f(x,y)$, i.e., find a string in $\underset{y \in \zo^{p(|x|)}}{\operatorname{argmin}}\ f(x, y)$.
	\begin{enumerate}[label=(\alph*)]
		\item Given a collection of sets $S_1, \dots, S_m \subseteq [n]$, a hitting set is a set $T$ such that $T \cap S_i \ne \emptyset$ for every $i = 1, \dots, m$. Describe how the task of finding a minimum-size hitting set can be stated as an $\NP$-minimization problem. (2 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
		\item Consider the decision problem $\mathprob{HS} = \{\langle n, k, S_1, \dots, S_m \rangle \mid \exists \text{ a hitting set for } S_1, \dots, S_m $ $\text{ of size } \le k\}$. Show that if $\mathprob{HS} \in \P$, then there is a poly-time algorithm for finding a minimum-size hitting set. (3 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
	
	
		\item	Show that $\P = \NP$ if and only if every $\NP$ minimization problem can be solved in polynomial time. (4 points)
		
		Hint: We showed in class that $\P = \NP$ iff every $\NP$ search problem can be solved in poly-time. You can use this fact without proof.
		
		\begin{solution}
			Your solution here.
		\end{solution}
	\end{enumerate}
\end{problem}

\begin{problem}[Sparse Languages]
	A language $L \in \zo^*$ is \emph{sparse} if there exists a polynomial $p(n)$ such that $|L \cap \zo^{\le n}| \le p(n)$ for every natural number $n$. That is, for every $n$, out of the $2^{n+1} - 1$ possible strings of length $\le n$, only polynomially many (a tiny fraction) are in $L$. In this problem, you will prove and explore some consequences of \emph{Fortune's Theorem}, which says that the existence of a $\coNP$-complete sparse language implies $\P = \NP$.
	
	So let's get started! Suppose there exists a $\coNP$-complete language $L$ such that there is a polynomial $p$ such that $|L \cap \zo^{\le n}| \le p(n)$ for every $n$. Consider the $\coNP$-complete language $\mathprob{TAUT} = \{\varphi \mid \varphi \text{ is a Boolean formula s.t. } \forall x \ \varphi(x) = 1\}$. Since $L$ is $\coNP$-complete, there is a poly-time reduction $f$ from $\mathprob{TAUT}$ to $L$, and therefore some polynomial $r$ such that $|f(\varphi)| \le r(|\varphi|)$ for every formula $\varphi$.
	\begin{enumerate}[label=(\alph*)]
		\item Briefly explain why, in order to prove Fortune's Theorem, it suffices to exhibit a poly-time algorithm for $\mathprob{TAUT}$. (1 point)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
	\end{enumerate}
		To give such an algorithm, first consider (as a thought experiment) building the downward self-reduction tree for an input formula. That is, given a Boolean formula $\varphi(x_1, \dots, x_n)$, let $\varphi_0 = \varphi(0, x_2, \dots, x_n)$ and $\varphi_1 = \varphi(1, x_2, \dots, x_n)$. Then $\varphi \in \mathprob{TAUT} \iff \varphi_0 \in \mathprob{TAUT}$ and $\varphi_1 \in \mathprob{TAUT}$. We can recurse on the formulas $\varphi_0$ and $\varphi_1$, ultimately giving us a tree of depth $n$ such that the original formula is a tautology iff all the leaves evaluate to $1$, but this takes exponential time as there are $2^n$ leaves.
		
		Instead, we're going to prune the tree as we explore it, ensuring that the number of formulas explored at each depth is bounded by a polynomial. We will take this polynomial to be (roughly) $t(n) := p(r(2n+5))$, for reasons that will hopefully become clear. Suppose that at some level of the tree, we've materialized a collection of ``active'' formulas $\varphi_0, \dots, \varphi_k$ such that $\varphi \in \mathprob{TAUT} \iff \varphi_i \in \mathprob{TAUT} \text{ for all } i = 0, 1, \dots, k$. If $k \le t(n)$, then we recurse on to the next level of the tree. Otherwise, if $k > t(n)$, we will prune the set of active formulas by one.
		
		Here's how to do the pruning. For each $i = 1, \dots, k$ (note that we are not including $i = 0$), let $s_i = f((\varphi_0) \land (\varphi_i))$. That is, we apply the reduction $f$ to the formula obtained by taking the logical AND of formulas $\varphi_0$ and $\varphi_i$.
		\begin{enumerate}[resume, label=(\alph*)]	
		\item Explain why if every active formula $\varphi_0, \dots, \varphi_k$ has length at most $n$, then every string $s_1, \dots, s_k$ has length at most $r(2n+5)$. (1 point)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
		\end{enumerate}
		Examining the collection of resulting strings $s_1, \dots, s_k$, there are two possible cases:
		
		\begin{description}
		\item[Case 1:] All strings $s_1, \dots, s_k$ are distinct. 
		\item[Case 2:] There exists a pair of strings $s_i, s_j$ where $s_i = s_j$ but $i \ne j$.
		\end{description}
		
	\begin{enumerate}[resume, label=(\alph*)]
		\item Show that in Case 1, we can automatically conclude that $\varphi$ is NOT a tautology, and therefore we can halt and reject. (2 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
	
		
		\item Show that in Case 2, it is safe to prune, say, the formula $\varphi_i$. That is, the original formula $\varphi$ is a tautology if and only if $\varphi_0, \dots, \varphi_{i-1}, \varphi_{i+1}, \dots, \varphi_k$ are all tautologies. (2 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
	
	
	\end{enumerate}
		Thus, if $k > t(n)$, our algorithm either halts or reduces the number of active formulas by 1.
		
	\begin{enumerate}[resume, label=(\alph*)]	
		\item Briefly analyze the runtime of this algorithm to conclude that it indeed decides $\mathprob{TAUT}$ in polynomial time. (2 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
		\item A natural question you might ask about $\mathprob{TAUT}$ (or $\SAT$ or whatever) is whether there is a poly-time algorithm that correctly solves it on \emph{most} instances. More specifically, let's say that an algorithm $A$ \emph{almost solves} $\mathprob{TAUT}$ (with one-sided error) if:
		\begin{itemize}
			\item $\varphi$ is not a tautology $\implies A(\varphi) = 0$. (I.e., $A$ always produces the correct answer of $0$ whenever $\varphi$ is not a tautology.)
			\item There exists a polynomial $p(n)$ such that for every $n$, we have $A(\varphi) = 0$ for at most $p(n)$ tautologies $\varphi$ of length at most $n$. (I.e., $A$ produces the correct answer of $1$ for all but polynomially many tautologies $\varphi$.)
		\end{itemize}
		Use Fortune's Theorem to show that if there is a poly-time algorithm that almost solves $\mathprob{TAUT}$ with one-sided error, then $\P = \NP$. (3 points)
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
		\item (*Bonus*) Show that the conclusion above holds even for algorithms $A$ with two-sided error. That is, if there is a polynomial $p(n)$ and a poly-time algorithm $A$ such that for every $n$,
		\begin{itemize}
			\item $A(\varphi) = 0$ for at most $p(n)$ tautologies $\varphi$ of length $n$, and
			\item $A(\varphi) = 1$ for at most $p(n)$ non-tautologies $\varphi$ of length $n$,
		\end{itemize}
		then $\P = \NP$.
		
		
		\begin{solution}
			Your solution here.
		\end{solution}
	\end{enumerate}
\end{problem}

\end{document}






