🎙 Free live masterclass · Sun, 29 Nov, 7:00 pm IST · Java Full Stack roadmap Register free →
Skills101
← All topics

Quiz: Decidability and Complexity: questions with answers

10 questions, each with the answer and a short explanation.

Take the timed quiz + get a certificate →
  1. Q1. Why can no program decide the halting problem?
  2. Q2. What does "NP" stand for?
  3. Q3. If someone found a polynomial-time algorithm for SAT, what would follow?
  4. Q4. Rice's theorem says which of these is undecidable in general?
  5. Q5. In the SAT demo, how many assignments might brute force need for n = 20 variables?
  6. Q6. The halting problem is:
  7. Q7. To prove a new problem B undecidable by reduction, you show that:
  8. Q8. Which property is decidable, according to Rice's theorem's limits?
  9. Q9. Which is the best description of an NP-complete problem?
  10. Q10. Why do static analysers and linters either miss some bugs or give false alarms?