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?

1. 3-SAT ≤p TSP. 2. If P ¹ NP, then 3-SAT ≤p 2-SAT. 3. If P ¹ NP, then no NP-complete problem can be solved in polynomial time.

Question

Engineering

Oren

17 August, 19:15

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?

1. 3-SAT ≤p TSP. 2. If P ¹ NP, then 3-SAT ≤p 2-SAT. 3. If P ¹ NP, then no NP-complete problem can be solved in polynomial time.

+2

Answers (1)

Know the Answer?

Catalina Juarez · Answer 1

3-SAT ≤p TSP

If P ¹ NP, then no NP-complete problem can be solved in polynomial time.

both the statements are true.

Explanation:

3-SAT ≤p TSP due to any complete problem of NP to other problem by exits of reductions. If P ¹ NP, then 3-SAT ≤p 2-SAT are the polynomial time algorithm are not for 3-SAT. In P, 2-SAT is found, 3 - SAT polynomial time algorithm implies the exit of reductions. 3 SAT does not have polynomial time algorithm when P≠NP. If P ¹ NP, then no NP-complete problem can be solved in polynomial time. because for the NP complete problem individually gets the polynomial time algorithm for the others. It may be in P for all the problems, the implication of latter is P≠NP.