🎙 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 9 of 10

Which is the best description of an NP-complete problem?

Which is the best description of an NP-complete problem?

  1. A.A problem that can never be solved
  2. B.Any problem in P
  3. C.A problem in NP to which every NP problem can be reduced in polynomial time
  4. 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 →