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

heoremstyle{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}

egin{document}

egin{center}

{Large CS 535: Complexity Theory, Fall 2020}

igskip

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

egin{problem}[$coNP$]

Recall that the complexity class $coNP$ consists of languages $L$ such that $overline{L} in NP$.

egin{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.

egin{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

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

egin{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 ext{ 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$.

egin{solution}

Your solution here.

end{solution}

end{enumerate}

end{problem}

ewpage

egin{problem}[Decision vs. Optimization]

An $NP$-optimization problem is specified by a polynomial-time computable objective function $f : {0, 1}^* imes {0, 1}^* o 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)$.

egin{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}