Undecidable Problems
Help Questions
AP Computer Science Principles › Undecidable Problems
In a passage about software verification, undecidable problems were described as having no algorithm that always halted with a correct decision; the Halting Problem asked whether a program stopped; this blocked perfect analyzers; NP-complete problems were different because they remained decidable though sometimes slow. What makes undecidable problems distinct from NP-complete problems according to the text?
Undecidable problems were easier than NP-complete problems because they avoided worst-case inputs.
Undecidable problems had no correct answers, while NP-complete problems always had one answer.
Undecidable problems were solved by randomness, while NP-complete problems required strict determinism.
Undecidable problems could not be decided by any always-correct terminating algorithm, unlike NP-complete problems.
Explanation
This question tests understanding of undecidable problems in algorithms and programming (AP CSP). The key distinction between undecidable and NP-complete problems lies in whether they can be solved by any algorithm at all - undecidable problems have no algorithm that always terminates with a correct answer, while NP-complete problems do have algorithms (though they may be exponentially slow). The passage emphasizes that the Halting Problem is undecidable, meaning no algorithm can always correctly determine if a program halts, whereas NP-complete problems remain decidable despite being computationally expensive. Choice B is correct because it captures this fundamental difference: undecidable problems lack any always-correct terminating algorithm, while NP-complete problems have such algorithms even if they're inefficient. Choice D is incorrect as it reverses the relationship - undecidable problems are actually harder than NP-complete problems in that they cannot be solved at all. To help students: Use a hierarchy diagram showing P ⊆ NP ⊆ Decidable problems, with undecidable problems outside this hierarchy entirely.
In a verification-focused passage, undecidable problems were defined as having no algorithm that always halted with correct answers; the Halting Problem asked whether code stopped; this blocked perfect bug-finding; NP-complete problems differed because they stayed decidable though potentially slow. What makes undecidable problems distinct from NP-complete problems according to the text?
Undecidable problems came from hardware limits, while NP-complete problems came from software style choices.
Undecidable problems were decidable but slower, while NP-complete problems were impossible to decide.
Undecidable problems lacked any always-correct terminating algorithm, while NP-complete problems still had one.
Undecidable problems were solved by heuristics, while NP-complete problems were solved instantly by compilers.
Explanation
This question tests understanding of undecidable problems in algorithms and programming (AP CSP). The fundamental distinction between undecidable and NP-complete problems is that undecidable problems have no algorithm that can solve them for all inputs, while NP-complete problems do have algorithms (though potentially exponentially slow ones). The passage emphasizes that the Halting Problem is undecidable, contrasting it with NP-complete problems that remain decidable despite computational challenges. Choice B is correct because it precisely captures this distinction: undecidable problems lack any always-correct terminating algorithm, while NP-complete problems still have one (even if inefficient). Choice A is incorrect as it reverses the relationship - NP-complete problems are decidable but potentially slow, while undecidable problems are impossible to decide algorithmically. To help students: Create examples showing that you can write a brute-force algorithm for any NP-complete problem, but you cannot write any algorithm for the Halting Problem that works on all inputs.