Description
1. In this question we examine the validity of verifiers and deciders for showing membership in
NP or P.
(a) Recall
LACC = {(hMi, x) : M is a TM that accepts x}
Is the program V a verifier for LACC, where the certificate C ≥ 1 is an integer represented
in binary? (Hint: Is V efficient?) Show why or why not.
V = “On input (hMi, x, C):
1. Run M on x for C steps
2. If M accepts x in those C steps, ACCEPT. Else, REJECT.”
Solution:
(b) Define
First-Digit-Factorial = {n ∈ N : the first digit of the decimal representation of n! is 2},
where the first digit is the most significant digit. Does F show that First-Digit-Factorial ∈
P? Show why or why not.
F = “On input n:
1. product ← 1
2. For i from 2 to n
3. product ← product · i
4. digit ← product
5. While digit ≥ 10
6. digit ← bdigit/10c
7. If digit = 2, ACCEPT. Else REJECT.”
Solution:
2. Show that the following languages are in the class NP.
Note: To prove that a language is in NP, you must provide a verifier and prove that your
verifier satisfies correctness and efficiency.
(a) Ham-Cycle = {hGi : G is an undirected graph with a Hamiltonian cycle}.
Note: a Hamiltonian cycle for a graph is a path that visits each node exactly once and
ends at the starting node.
Solution:
(b) For two graphs G = (V, E), G0 = (V
0
, E0
), an isomorphism between them is a bijection
γ : V → V
0
such that (a, b) ∈ E if and only if (γ(a), γ(b)) ∈ E0
.
Similarly, G and G0 are
said to be isomorphic if there exists an isomorphism between them.
For example, the following two graphs are isomorphic, by the bijection γ where γ(1) =
1, γ(2) = 3, γ(3) = 5, γ(4) = 2, γ(5) = 4.
1 2
3
4
5
1 2
3
4
5
Define Graph-Isomorphism = {(hGi,hHi) : G, H are isomorphic graphs}.
Solution:
(c) Define Not-Prime = {n ∈ N : n is not a prime number}
Solution:
3. (a) Let A, B be two languages in P. Then show the language A ∪ B is also in P.
Solution:
(b) Let A, B be two languages in NP. Then show the language A ∪ B is also in NP.
Solution:
(c) Let A, B ∈ P. Define AB = {ab : a ∈ A, b ∈ B} where ab denotes the concatenation of
a and b. For example, if a = 100111 and b = 0011 are bitstrings then ab = 1001110011.
Show that AB ∈ P.
Solution:
4. This question explores the complexity class coNP =
L
L ∈ NP
. Conceptually, NP contains
the languages whose “yes” instances can be verified efficiently, whereas coNP contains the
languages whose “no” instances can be verified efficiently.
(a) Prove that P is closed under set complement. That is, for any L ∈ P, we have L ∈ P.
Solution:
(b) Use part (a) to prove that if P = NP, the following set inclusions hold: (i) NP ⊆ coNP
(that is, for any L ∈ NP, we have L ∈ coNP), and (ii) coNP ⊆ NP.
Solution:
(c) Conclude from part (b) that if NP 6= coNP, then P 6= NP.
Solution: