Which of the following is an NP-complete problem?
2017
Which of the following is an NP-complete problem?
Answer: B. CNF-Satisfiability problem — The correct option is B (CNF-Satisfiability problem). By Cook's Theorem, the Boolean satisfiability problem (SAT), specifically in CNF form, is the…
- A.
Turing’s Halting problem
- B.
CNF-Satisfiability problem
- C.
Presburger Arithmetic problem
- D.
Number of Hamiltonian circuits in a complete graph of ‘n’ vertices with n > 2
Attempted by 37 students.
Show answer & explanation
Correct answer: B
The correct option is B (CNF-Satisfiability problem). By Cook's Theorem, the Boolean satisfiability problem (SAT), specifically in CNF form, is the foundational NP-complete problem. It belongs to the class NP and every other problem in NP can be reduced to it in polynomial time.
Explore the full course: Iocl Engineers Officers Grade A Paper 2