A. If some NP-complete problem P is in P then P = NP B. TSP is in NP C. SAT is…
2023
A. If some NP-complete problem P is in P then P = NP
B. TSP is in NP
C. SAT is in NP
D. Hamilton circuit problem is not NP-complete
Choose the correct answer from the options given below:
- A.
A, B and C only
- B.
B, C and D only
- C.
C, D and A only
- D.
D, A and B only
Attempted by 8 students.
Show answer & explanation
Correct answer: A
A. If some NP-complete problem P is in P then P = NP
✔ True — this is a fundamental result in complexity theory.
B. TSP is in NP
✔ True — a given tour can be verified in polynomial time.
C. SAT is in NP
✔ True — a truth assignment can be checked in polynomial time.
D. Hamilton circuit problem is not NP-complete
✖ False — Hamiltonian Cycle is NP-complete.
✅ Correct Answer: Option A — A, B and C only
A video solution is available for this question — log in and enroll to watch it.