← Quiz: Decidability and Complexity: all 10 questions
Quiz: Decidability and Complexity · Question 9 of 10
Which is the best description of an NP-complete problem?
Which is the best description of an NP-complete problem?
- A.A problem that can never be solved
- B.Any problem in P
- C.A problem in NP to which every NP problem can be reduced in polynomial time
- D.A problem that needs exponential memory
Answer & explanation
Correct answer: A problem in NP to which every NP problem can be reduced in polynomial time
Solving any NP-complete problem in polynomial time would give P = NP.
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 →