Final answer:
If a problem is NP-complete it can be reduced to the Travelling Salesperson problem; if a problem has a polynomial time solution, it also has a polynomial time verifier; and any problem with a polynomial time verifier can be reduced to 3-SAT.
Step-by-step explanation:
Let's analyze each statement:
a. This statement is false. If a problem in NP can be solved in polynomial time, it means that it is not NP-complete. NP-complete problems are the hardest problems in NP, and if one of them can be solved in polynomial time, it implies that all NP-complete problems can be solved in polynomial time.
b. This statement is true. Every problem that is NP-complete can be reduced to the Travelling Salesperson problem. This means that if we can solve the Travelling Salesperson problem efficiently, we can solve any NP-complete problem efficiently as well.
c. This statement is true. If a problem can be solved in polynomial time, it means that there exists a polynomial time algorithm to verify the solution. The verification process itself takes polynomial time.
d. This statement is false. Not every problem in P can be reduced to an NP-complete problem. NP-complete problems are harder than problems in P, so it is not possible to reduce every problem in P to an NP-complete problem.
e. This statement is true. Every problem with a polynomial time verifier can be reduced to 3-SAT. 3-SAT is an NP-complete problem, so any problem that can be verified in polynomial time can also be reduced to 3-SAT.
In summary, the true statements are: b, c, and e.