Question

3. (3 pts) Two well-known NP-complete problems are 3-SAT and TSP, the traveling salesman problem. The 2-SAT problem is a SAT variant in which each clause contains at most two literals. 2-SAT is known to have a polynomial-time algorithm. Is each of the following statements true or false? Justify your answer. a. 3-SAT sp TSP. b. If P NP, then 3-SAT Sp 2-SAT. C. If P NP, then no NP-complete problem can be solved in polynomial time.

Answer 1

ANSWER:

GIVEN THAT:

Two well-known NP-complete problems are 3-SAT and TSP:

1) 3-SAT ≤p TSP.

TRUE:

There exists a reduction from any NP-complete problem to any other such problem.

2)If P is not equal to NP, then 3-SAT ≤p 2-SAT.

FALSE:

If , there is no polynomial-time algorithm for 3-SAT. However, 2-SAT is known to be in P; if the reduction existed,it would imply a polynomial-time algorithm for 3-SAT.

PNP

3)If P is not equal to NP, then no NP-complete problem can be solved in polynomial time.

TRUE:

A polynomial-time algorithm for one NP-complete problem yields polynomial-time algorithms for all others. Hence, either all these problems are in P, or none are. implies the latter.

PNP