CS计算机代考程序代写 Sample of Final Exam of cs 6382

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