%
% 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}