%
% 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{enumerate}
\usepackage{comment}
\usepackage{amsmath,amssymb,amsthm}

\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 2020}

\bigskip

{\Large Homework 2}

\smallskip

Due: 8:00PM, Friday, September 18, 2020.

\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.


\begin{problem}[$\coNP$]
Recall that the complexity class $\coNP$ consists of languages $L$ such that $\overline{L} \in \NP$.
	\begin{enumerate}[(a)]
		\item Show that a language $L$ is $\NP$-complete if and only if $\overline{L}$ is $\coNP$-complete. Recall that completeness for both classes is defined with respect to polynomial-time (Karp) reductions.
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
		\item In the discrete art gallery problem, there are $n$ paintings numbered $1, \dots, n$ and $m$ guard posts. A guard stationed at guard post $i$ is able to see some set $S_i \subseteq [n]$ of paintings. An art gallery is $k$-\emph{vulnerable} if for every assignment of $k$ guards to guard posts, there exists a painting that none of those guards can see. That is, define
		\[\mathprob{VUL} = \{\langle S_1, \dots, S_m, n, k \rangle \mid \forall T \subseteq [m], |T| = k \quad \exists j \in [n], j \notin \cup_{i \in T} S_i\}.\]
		Prove that $\mathprob{VUL}$ is $\coNP$-complete.
		
		\smallskip
		
		Hint: You may use, without proof, the fact that $\mathprob{VERTEXCOVER}$ is $\NP$-complete.
		
		\begin{solution}
			Your solution here.
		\end{solution}
		
		\item Find the first error in the following ``proof'' that $\NP = \coNP$, and explain why it is an error:
		Let $M$ be a nondeterministic polynomial-time algorithm computing $\SAT$. We design a nondeterministic polynomial-time algorithm computing
		\[\mathprob{UNSAT} = \{\varphi \text{ a CNF formula } \mid \forall x \ \varphi(x) = 0\}\]
		as follows. On input $\varphi$ (an instance of $\mathprob{UNSAT}$), evaluate $b = M(\varphi)$. If $b = 0$, output $1$, and if $b = 1$, output $0$. This runs in nondeterministic polynomial-time as long as $M$ does, and $\varphi \in \SAT$ iff $\varphi \notin \mathprob{UNSAT}$, so it decides $\mathprob{UNSAT}$. Therefore, $\mathprob{UNSAT} \in \NP$. Since $\mathprob{UNSAT}$ is $\coNP$-complete, it follows that $\coNP \subseteq \NP$. A similar argument shows that $\NP \subseteq \coNP$, hence $\NP = \coNP$.
		
		\begin{solution}
			Your solution here.
		\end{solution}
	\end{enumerate}
\end{problem}

\newpage

\begin{problem}[Decision vs. Optimization]
	An $\NP$-optimization problem is specified by a polynomial-time computable objective function $f : \{0, 1\}^* \times \{0, 1\}^* \to \N$ and a polynomial $p$. Given an input $x \in \zo^*$, let $Y_x = \{y \in \zo^* \mid |y| \le p(|x|)\}$. The problem is to find a $y \in Y_x$ that maximizes $f(x,y)$, i.e., find a string in $\underset{y \in Y_x}{\operatorname{argmax}}\ f(x, y)$.
	\begin{enumerate}[(a)]
	\item Formulate the problem of finding a largest independent set in a graph as an $\NP$-optimization problem.
	\item	Show that $\P = \NP$ if and only if every $\NP$-optimization problem can be solved in polynomial time.
	
	\smallskip
	
	Hint: It may help to think about how you would use a polynomial-time algorithm for $\mathprob{INDSET}$ to solve the problem from part (a).
	\end{enumerate}
\end{problem}
\end{document}






