Description
Problem 1 (20 points)
Let G be undirected and connected graph. A graph is said to be
connected if every pair of vertices in the graph are connected by a
path. A path is called an Eulerian path if it starts and ends at a
same vertex and all edges in G appear on the path exactly once.
The Eulerian path problem is defined as follows.
EULERIAN−PATH = { hGi | G has an Eulerian path }
Prove that EULERIAN−PATH is in P.
Hint: Prove that G has an Eulerian path if and only if every vertex
in G has even number of degree, i.e., every vertex is in touch with
an even number of edges. One direction is easy. Use induction to
prove the other.
2 / 6
CS 331: Theory of Computing
Problem 2 (20 points)
Let G be undirected graph whose every edge is associated with an
integer (length). The Traveling Salesman Problem is defined as
follows.
TSP = { hG, ki | G has a Hamiltonian path of length less than k }
Prove that TSP is NP-complete.
Hint: Prove that HAMILTON−PATH ≤P TSP.
3 / 6
CS 331: Theory of Computing
Problem 3 (20 points)
A disqualifier for a language L is DTM D, where
L = { w | D accepts hw, ei for some word e }.
D is polynomial time disqualifier if D runs in polynomial time in
the length of w. A language L is polynomially disqualifiable if it
has a polynomial time disqualifier.
Prove that a language is in coNP iff it has a polynomial time
disqualifier.
4 / 6
CS 331: Theory of Computing
Problem 4 (20 points)
A language L is coNP-complete if
L ∈ coNP, and
for any language L 0 ∈ coNP, L 0 ≤P L .
Prove the following statements.
(10 points) The class coNP is closed under polynomial-time
reductions; that is, if L1 ≤P L2 and L2 ∈ coNP, then L1 ∈ coNP.
(10 points) If a coNP-complete language L is in NP, then
coNP = NP.
5 / 6
CS 331: Theory of Computing
Problem 5 (20 points)
Let P
L be the class of languages recognized by polynomial time
oracle Turing machines with an oracle for the language L . Let C
be a class of languages. Define P
C =
S
L ∈C P
L ; that is, P
C
is the
class of languages recognized by polynomial time oracle Turing
machines that use oracles for languages in C.
Prove the following statements.
(5 points) For any language class C, P
C
is closed under
complementation; that is, L ∈ P
C
iff L ∈ P
C
.
(5 points) For any language class C that is closed under
complementation, C ⊆ coNP iff C ⊆ NP.
(5 points) P
P ⊆ P.
(5 points) NPP ⊆ NP.
6 / 6
CS 331: Theory of Computing
