CMPSC464 Name:
Midterm Exam 2
11/04/2021
Time Limit: 75 Minutes
Copyright By PowCoder代写 加微信 powcoder
This exam contains 10 pages (including this cover page, double-sided) and 6 questions.
Total of points is 100.
This will contribute to 25 % of your total grade
Grade Table (for grader use only)
Question Points Score
Total: 100
CMPSC464 Midterm Exam 2 – Page 2 of 10 11/04/2021
1. (25 points) True or False Questions (Leaving an empty box will result in 0 pt)
(a) (1 point) 3SAT is in NP.
(b) (1 point) 2SAT is in NP.
(c) (1 point) If L is NP-hard and is in NP, then L is NP-complete.
(d) (1 point) If there exists a language L that is in NP, but not in P, then P is equal
(e) (1 point) Graph Isomorphism is known to be in P.
(f) (1 point) If a NP-complete language is in P, then P is equal to NP.
(g) (1 point) If L is in NTIME(T (n)), then it is known to be in DTIME(T (n)).
(h) (1 point) CLIQUE is NP-complete.
(i) (1 point) 3SAT is NP-hard.
(j) (1 point) If 3SAT is in P then P is not equal to NP.
CMPSC464 Midterm Exam 2 – Page 3 of 10 11/04/2021
(k) (1 point) Cook- states that 3SAT is NP-complete.
(l) (1 point) k-SAT with k ≥ 2 are all NP-complete.
(m) (1 point) If L is NP-complete, then 3SAT≤p L
(n) (1 point) Suppose A ≤p B, then B ≤p A.
(o) (1 point) If A ≤p B and B ≤p C then A ≤p C.
(p) (2 points) All NP languages are known to be NP-complete.
(q) (2 points) Any L in NP can be decided by a deterministic Turing machine in 2n
time for some c > 1.
(r) (2 points) Any L in P can be solved by a non-deterministic Turing machine in
O(log n)-time.
(s) (2 points) Suppose there exists a language L that is in NP, but not in P. Then all
NP-complete languages are not in P.
(t) (2 points) FACTORING is known to be NP-complete.
CMPSC464 Midterm Exam 2 – Page 4 of 10 11/04/2021
2. (15 points) Show that the respective languages are in P. Leaving Blank will result in 1
point each.
(a) (5 points) CONNECTED – the set of all connected graphs.
(b) (5 points) TRIANGLEFREE – the set of all graphs that do not contain a triangle
(i.e. a 3-clique)
(c) (5 points) Suppose A is in P . Then show that Ac (A complement) is also in P.
CMPSC464 Midterm Exam 2 – Page 5 of 10 11/04/2021
3. (20 points) Show that the respective languages are in NP. Leaving Blank will result in
1 point each.
(a) (5 points) k-CLIQUE – the set of all graphs containing k-sized clique.
(b) (5 points) k-INDSET – the set of all graphs containing independent set of size k.
CMPSC464 Midterm Exam 2 – Page 6 of 10 11/04/2021
(c) (10 points) Let A be some language in NP. Show that A∗ is in NP as well. Leaving
Blank will result in 2 points.
CMPSC464 Midterm Exam 2 – Page 7 of 10 11/04/2021
4. (10 points) Recall that Independent Set composes of (G, k) pairs where G contains an
independent set of size k. Show that Independent Set is NP-hard. You may assume that
Vertex Cover and CLIQUE are NP-complete. Leaving Blank will result in 2 points.
CMPSC464 Midterm Exam 2 – Page 8 of 10 11/04/2021
5. (15 points) Suppose SAT is in P. Then define SAT2 as the set of Boolean SAT formula
with at least two satisfying assignments. Then show that SAT2 is in P as well. Leaving
Blank will result in 3 points.
CMPSC464 Midterm Exam 2 – Page 9 of 10 11/04/2021
6. (15 points) Define integer programs as a list of m linear inequalities with rational coeffi-
cients over n variables x1, . . . , xn. We say that the integer program is satisfiable if there
exists {0, 1} assignments to x1, . . . , xn that satisfies all linear inequalities.
For example the following integer program is satisfiable by assigning x1, x2 = 1 and
x1 + x2 ≥ 2
x1 + x3 ≤ 1
x2 + x3 ≤ 1
Let 0/1-IPROG be the set of satisfiable 0/1 integer programs. The goal of this problem
is to show that 0/1 IPROG is NP-complete.
(a) (5 points) Show that 0/1-IPROG is in NP. Leaving Blank will result in 1 point.
CMPSC464 Midterm Exam 2 – Page 10 of 10 11/04/2021
(b) (10 points) Now show that 0/1-IPROG is NP-hard. (Hint: You can use Cook- as given) Leaving Blank will result in 2 points.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com