Search for question
Question

1. For the following statements, deduce whether they are true or false, and provide a brief

explanation.

(a) If A, B are NP-Complete, then A Sp B and B Sp A.

(b) If A € NP, then A & P.

(c) If A is NP-Hard and A € P, then A is NP-Complete.

(d) If A in NP-Complete and A can be reduced to a problem B € NP, then B is also NP-

Complete.

(e) P U NP-Complete= NP.

(f) Suppose that P = NP. Then, there exists a polynomial time algorithm for Independent-

Set.

(g) Define the PALINDROME problem as checking whether an all-lowercase string is a

palindrome (equal when reversed). PALINDROME is in P.

(h) Define the VERTEX-COVER-MINI as a problem similar to VERTEX-COVER, but the

graph G is assumed to have the property that the degree of all its vertices are at most

2. VERTEX-COVER-MINI is not in P.

(i) Define the VERTEX-COVER-MINI-2 as a problem similar to VERTEX-COVER, but

the graph G are assumed to be a binary tree. VERTEX-COVER-MINI-2 is not in P.