CS 535: Complexity Theory, Fall 2020 Homework 2
Due: 8:00PM, Friday, September 18, 2020.
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 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.
Problem 1 (coNP). Recall that the complexity class coNP consists of languages L such that L ∈ NP.
(a) Show that a language L is NP-complete if and only if L is coNP-complete. Recall that completeness for both classes is defined with respect to polynomial-time (Karp) reductions.
(b) In the discrete art gallery problem, there are n paintings numbered 1, . . . , n and m guard posts. A guard stationed at guard post i is able to see some set Si ⊆ [n] of paintings. An art gallery is k-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
VUL = {⟨S1,…,Sm,n,k⟩ | ∀T ⊆ [m],|T| = k ∃j ∈ [n],j ∈/ ∪i∈TSi}.
Prove that VUL is coNP-complete.
Hint: You may use, without proof, the fact that VERTEXCOVER is NP-complete.
(c) 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
UNSAT={φaCNFformula |∀xφ(x)=0}
as follows. On input φ (an instance of UNSAT), evaluate b = M(φ). If b = 0, output 1, and if b = 1, output 0. This runs in nondeterministic polynomial-time as long as M does, and φ ∈ SAT iff φ ∈/ UNSAT, so it decides UNSAT. Therefore, UNSAT ∈ NP. Since UNSAT is coNP-complete, it follows that coNP ⊆ NP. A similar argument shows that NP ⊆ coNP, hence NP = coNP.
1
Problem 2 (Decision vs. Optimization). An NP-optimization problem is specified by a polynomial-time computable objective function f : {0, 1}∗ × {0, 1}∗ → N and a polynomial p. Given an input x ∈ {0,1}∗, let Yx = {y ∈ {0,1}∗ | |y| ≤ p(|x|)}. The problem is to find a y ∈ Yx that maximizes f (x, y), i.e., find a string in argmax f (x, y).
y∈Yx
(a) Formulate the problem of finding a largest independent set in a graph as an NP-
optimization problem.
(b) Show that P = NP if and only if every NP-optimization problem can be solved in polynomial time.
Hint: It may help to think about how you would use a polynomial-time algorithm for INDSET to solve the problem from part (a).
2