🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← Quiz: Decidability and Complexity: all 10 questions

Quiz: Decidability and Complexity · Question 3 of 10

If someone found a polynomial-time algorithm for SAT, what would follow?

If someone found a polynomial-time algorithm for SAT, what would follow?

  1. A.Nothing
  2. B.The halting problem becomes decidable
  3. C.P = NP, since SAT is NP-complete
  4. D.Only SAT becomes easier
Answer & explanation

Correct answer: P = NP, since SAT is NP-complete

Every NP problem reduces to SAT in polynomial time.

Can you get the rest right without peeking?

Take the timed Quiz: Decidability and Complexity quiz free. Pass it to earn XP and count towards your certificate.

Start the quiz →