Question

Which of the following accurately describes the Cook-Levin Theorem? Every problem that can be verified in polynomial time can be solved in polynomial time. Every Turing Machine problem can be

polynomially reduced to an instance of SAT. The Boolean Satisfiability problem SAT is NP-complete. The Halting problem for Turing Machines is undecidable.

Fig: 1

Fig: 2

Fig: 3

Fig: 4

Fig: 5