Sample of Final Exam of cs 6382
(Open book and open notes)
1. (20 pts) Show that the following problem is P -complete: Given an DTM M , an input x, and
a string 0t, determine whether M on input x halts within t moves.
2. (20 pts) Show that the following problem is #P -complete: Given an NTM M , an input x,
and a string 0t, find the number of computation paths of M on input x, which halts within
t moves. .
3. (20 pts) Is following problem APX-hard?
Given two collections C and D of subsets of finite set X and a positive integer d, find a
subset A of X, with |A| ≤ d, to maximize |{C ∈ C | A ∩ C = ∅} ∪ {D ∈ D | A ∩D 6= ∅}|.
4. (20 pts) Show that if NP 6= P, then following problem does not have a polynomial-time
(ρ lnn)-approximation for 0 < ρ < 1/2: Give a CNF F , find an assignment to satisfy F and
to minimize the number of variables which are assigned with 1.
5. (20 pts) Given a collection of subsets of a finite set X, find a maximum subcollection C′
of subsets in C such that for any two subsets A and B in C′, A ∩ B 6= ∅. Show that this
problem has no polynomial-time
√
n-approximation unless NP=P.
1