[SOLVED] CS algorithm %

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

definclsolns{0}
documentclass[12pt]{article}

usepackage{fullpage}
usepackage{graphicx}
usepackage{enumerate}
usepackage{comment}
usepackage{amsmath,amssymb,amsthm}

input{macros}

theoremstyle{definition}

ifnuminclsolns=1
ewenvironment{solution}{paragraph{Solution.}}{}
else
ewenvironment{solution}{}{}
excludecomment{solution}
fi

makeatletter
defcollaborators#1{gdef@collaborators{#1}}
def@collaborators{@latex@warning@no@line{No
oexpandcollaborators 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}

ifnuminclsolns=1
makeatletter
oindent 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
otin 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
otin 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}

ewpage

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.
itemShow 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}