← 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?
- A.Nothing
- B.The halting problem becomes decidable
- C.P = NP, since SAT is NP-complete
- 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 →