Microsoft Word – coms4236final
1
COMS4236: Introduction to Computational Complexity, Spring 2014
Final Exam, due Monday May 12, 3pm at my office (CSB 455) or at
Sophie Majewski’s office (CSB 455B) or by e-mail
Rules: You can use your notes and the required and recommended textbooks, but you
cannot consult any other source (e.g. no other book, paper, the web, or any other person).
No collaboration is allowed.
Write clearly your name and UNI at the top of your exam.
Be clear, precise and succinct in your answers. You will be graded not only on the
correctness of your answers, but also on the clarity with which you express them.
Be neat.
Good luck!
2
Problem 1 [23 points]
In the Weighted Maximum Satisfiability (W-MAX-3SAT) problem we are given as input
a set of clauses, where each clause is the disjunction of 3 literals, and a positive integer
weight for each clause; the weights are given in binary. The value of a truth assignment is
the sum of the weights of the clauses that it satisfies. The problem is to compute a truth
assignment that has maximum value, i.e. that maximizes the sum of the weights of the
satisfied clauses.
1. Suppose that P=NP. Show that the following problems can be solved in polynomial
time.
a. [5 points] Given an instance of W-MAX-3SAT, compute the optimal value, i.e. the
maximum total weight of clauses satisfied by any truth assignment.
b. [5 points] Given an instance of W-MAX-3SAT, compute an optimal truth assignment.
c. [5 points] Given an instance of W-MAX-3SAT, determine if there is a unique optimal
truth assignment.
2. [8 points] Suppose that we have a polynomial time algorithm for problem c of part 1.
Show that P=NP.
Problem 2 [22 points]
1. [7 points] Show that P = L (= SPACE(logn)) implies that P ≠ PSPACE.
1. [8 points] Show that SPACE( n ) P implies that P = PSPACE.
2. [7 points] Consider the following problem.
Input: A positive integer N in binary.
Question: Is N the product of two primes?
Show that if this problem is NP-complete then NP=coNP.
Problem 3 [18 points]
We are given three nn matrices A,B,C with integer entries and we want to test if AB=C.
The straightforward way is to multiply the two matrices A,B and compare the result with
C. This takes O(n3) time if we use the standard matrix multiplication algorithm and
O(n2.376) time if we use the fastest known matrix multiplication algorithm.
Give a randomized algorithm that runs in O(n2) time. The algorithm should return ‘yes’
with probability 1 if AB=C, and should return ‘no’ with probability ≥ 0.99 if AB≠C.
(Hint: Consider the expression xCy, where x is a row vector and y a column vector of
variables and use Schwartz-Zippel.)
3
Problem 4 [17 points]
Consider the following SCG problem:
Input: A directed graph G.
Question: Is the graph G strongly connected, i.e. is it true that for every pair of nodes u,v
there is a path from u to v in G?
Classify the complexity of the SCG problem; i.e., identify a complexity class V for
which the problem is complete. Remember to prove both parts: that the problem belongs
to the class V, and that it is V -hard.
(If you cannot show completeness for any class, place the language in as low a class as
you can, for partial credit.)
Problem 5 [20 points]
A hypergraph H=(N,E) consists of a finite set N of nodes and a finite set E of
hyperedges, where each hyperedge is a subset of N. Hypergraphs are more general than
(undirected) graphs: in a graph all the edges have cardinality 2 (every edge consists of 2
nodes), whereas in a hypergraph, the hyperedges can have arbitrary cardinalities. A legal
coloring of a hypergraph is an assignment of colors to its nodes so that there is no
monochromatic hyperedge, i.e., there is no hyperedge all of whose nodes have the same
color. For example, if H is the hypergraph with set of nodes N={1,2,3,4} and set of
hyperedges E={ {1,2,3}, {1,3,4}, {2,3}, {2,4} }, then the coloring that assigns blue to
nodes 1, 2 and red to nodes 3, 4 is a legal coloring.
Consider the following Hypergraph 2-Coloring Game played on a hypergraph H=(N,E)
where N={1,…,n}, by two players, Player 1 and Player 2. The goal of Player 1 is to color
the hypergraph legally with 2 colors, red and blue, while the goal of Player 2 is to
produce an illegal 2-coloring. The game is played in rounds. In round i=1,…,n, if i is odd
then Player 1 chooses a color (red or blue) for node i, and if i is even then Player 2
chooses a color (red or blue) for node i. If at the end, the hypergraph has been legally
colored, then Player 1 wins, otherwise Player 2 wins.
The Hypergraph 2-Coloring Game Problem is the following problem.
Input: Hypergaph H=(N,E), where N={1,…,n}
Question: Does Player 1 have a winning strategy?
Show that the Hypergraph 2-Coloring Game Problem is PSPACE-complete. Remember
to prove both parts: that it belongs to PSPACE, and that it is PSPACE-hard.
(Hint: For the membership part, give a recursive algorithm. For the hardness part, reduce
from QSAT. )