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