Wednesday, February 6
-
Homework 7, due 2/6, 4:00pm.
-
Student S proposes the following algorithm to compute
a clique C of maximum size in a graph G.
- Initialize C to the empty set.
- Repeat the following 3 steps until G is empty.
- Choose a vertex v of highest degree in the graph and
add v to C.
- Remove (from G) every vertex w != v that is not adjacent
to v and remove all edges incident with w.
- Remove v and all edges incident with v from G.
- Briefly explain why student S's algorithm always computes
a clique C of G.
- Explain in a couple of lines why student S would become rich and
incredibly famous if this algorithm would always compute a clique
of maximum size.
- Crush student S's dreams of fame and fortune,
by showing that this algorithm does not
always compute a clique of maximum size.
-
Let UNARY-SUBSET-SUM be the subset sum problem in which all numbers
are represented in unary. (You may assume that all numbers involved
are natural numbers.)
- Why does the proof of Theorem 7.56 fail to show
that UNARY-SUBSET-SUM is NP-complete?
- Show that UNARY-SUBSET-SUM is in P.
Hint: Use dynamic programming. Make sure you explain your algorithm
and why it is in P.
-
Show that if NP is not equal to coNP then PSPACE
is not equal to the union of NP and coNP.
Big hint: Prove this by contradiction and think about where TQBF goes.
All you need to know about TQBF is that it is PSPACE-complete.
-
Show that EQNFA (equivalence between NFAs) is in PSPACE.
(Two NFAs are equivalent if they accept the same language.)
You may want to have a look at Example 8.4 first.
-
Wednesday, February 13
-
Homework 8, due 2/13, 4:00pm.
Do four of the following six questions. (If you do more than four questions,
your best four questions will count.)
- Problem 8.18.
-
Show that { < G, s, t, k > | G is a directed graph, s and t are vertices in G,
and the length of a shortest path from s to t is k} is NL-complete.
- Look at Sipser's proof of Theorem 8.27 (NL = coNL).
In class, we decided that we could probably modify
Sipser's algorithm to avoid the second loop (the one starting at line 13).
Do so. Try to follow Sipser's notation as much as possible and add
comments so that I can understand your algorithm.
-
EQNFA (from the previous homework) is PSPACE-complete.
Find out whose result this is, and give the journal reference.
-
A language A is self-reducible if
there is a polynomial-time oracle Turing machine M (see Definition 9.17)
such that A = MA and such that M on inputs of
length n queries only strings of length < n.
-
Show that QBF is self-reducible.
-
Show that every self-reducible language is in PSPACE.
-
PNP[log] is a subset of
PNP. It consists of all
languages in PNP such that the P-machine
queries its NP oracle O(log n) times.
PttNP is also a subset of
PNP. It consists of all
languages in PNP such that the P-machine
can query one list of strings to its NP oracle.
The oracle will give back a list of answers.
ODDSAT is the following problem:
Given a list of Boolean formulas,
is the number of satisfiable formulas in the list odd?
- Show that ODDSAT is in PttNP.
- Show that ODDSAT is in PNP[log].
- In fact, PNP[log] = PttNP.
One of the inclusions is easy to show. State the easy
inclusion and show it.
- For extra credit, show the converse inclusion.
Complexity and Computability