Description
1. Suppose A ≤L B using the reduction function f. Given w, an instance of
A, what is an upper bound on |f(w)| in terms of |w|?
2. Show that ANF A is NL-complete.
ANF A = {⟨N, w⟩| N is an NFA that accepts the string w}
3. Show that 2-SAT is NL-complete.
4. A ladder is a sequence of strings s1, s2, . . . , sk, wherein every string differs from the preceding one in exactly one character. For example, the
following is a ladder of English words, starting with the word “head” and
ending with the word “free”.
head, hear, near, fear, bear, beer, deer, deed, feed, feet, fret,
free.
Let LADDERDF A = {⟨M, s, t⟩| M is a DFA and L(M) contains a ladder
of strings, starting with s and ending with t}. Show that LADDERDF A
is in PSPACE.
5. If A ∈P, then show that PA =P.
6. A directed graph is strongly connected if for every pair of vertices (u, v)
there is a directed path from u to v in G. Show that the problem of
deciding if a graph is strongly connected is NL-complete.
7. For a language L ⊆ {0, 1}
∗
, and a function f(n) (assuming f(n) can
be computed in time O(f(n)), let Lf ⊆ {0, 1, #}
∗ denote the following
language:
Lf := {x#f(|x|)
|x ∈ L}
• Suppose that that L ∈ DTIME(f(n)). Then show that Lf ∈ DTIME(O(n)).
• Show that if f(n) is a polynomial function, then L ∈ P if and only if
Lf ∈ P.
• Show that P ̸= DSPACE(O(n)).
Hint: Assume an equality and arrive at a contradiction via suitable
padding and the Space Hierarchy Theorem.
• Define the class NEXP as
NEXP := [
k
NTIME
2
n
k
Prove that if P = NP then EXP = NEXP.
8. Show that if Σk = Πk for some k, then polynomial hierarchy collapses to
Σk.
9. What is the count (number) of functions f : {0, 1}
n → {0, 1} that are
both monotone and symmetric?