Undecidable Problems
Help Questions
AP Computer Science Principles › Undecidable Problems
What made undecidable problems distinct from NP-complete problems, as described in the passage for AP students?
Undecidable problems became decidable if $P=NP$, while NP-complete problems became undecidable if $P\ne NP$.
Undecidable problems lacked any correct algorithm for all cases, while NP-complete problems still had algorithms.
Undecidable problems were always solved quickly, while NP-complete problems always required exponential time.
Undecidable problems were in NP, while NP-complete problems were outside NP by definition.
Explanation
This question tests understanding of undecidable problems in algorithms and programming (AP CSP). The key distinction is that undecidable problems have no algorithm that can solve them for all inputs, while NP-complete problems do have algorithms (though they may be inefficient). The passage clarifies this fundamental difference in computability. Choice A is correct because it accurately captures that undecidable problems lack any correct algorithm for all cases, while NP-complete problems have algorithms (even if exponentially slow). Choice B is incorrect as it reverses the relationship - undecidable problems cannot be solved quickly because they cannot be solved at all algorithmically. To help students: Create a comparison chart showing undecidable vs NP-complete properties. Use concrete examples like the Halting Problem (undecidable) versus the Traveling Salesman Problem (NP-complete) to illustrate the difference.
According to an AP-level educational guide, what defined an undecidable problem in computing and programming?
A problem that was solvable only by trying all answers, so it belonged to NP-complete.
A problem that became solvable once enough memory and time were available to run the program.
A problem that no algorithm could solve correctly for every possible input, even in principle.
A problem that always lacked a solution because its question had no meaningful answer.
Explanation
This question tests understanding of undecidable problems in algorithms and programming (AP CSP). An undecidable problem is one for which no algorithm exists that can provide a correct yes/no answer for every possible input, even with unlimited time and resources. The passage focuses on this fundamental limitation in computation theory. Choice A is correct because it precisely defines undecidability - the impossibility of creating an algorithm that works correctly for all inputs, even in principle. Choice C is incorrect as it confuses undecidability with NP-completeness; NP-complete problems still have algorithms that work, they're just inefficient. To help students: Create a clear distinction between 'no algorithm exists' (undecidable) and 'no efficient algorithm exists' (NP-complete). Use visual diagrams showing the hierarchy of problem classes to reinforce these differences.
In the passage’s comparison, why did NP-complete problems not count as undecidable problems in general?
They were defined by infinite loops, so they were simply alternate names for the Halting Problem.
They were undecidable only until a faster computer appeared, after which every instance became easy.
They had no correct algorithms at all, so they matched undecidable problems exactly in computability.
They still had algorithms that solved every instance eventually, even if the time required could be impractical.
Explanation
This question tests understanding of undecidable problems in algorithms and programming (AP CSP). NP-complete problems are fundamentally different from undecidable problems because they do have algorithms that solve them - these algorithms just take exponential time in the worst case. The passage clarifies this distinction between computational difficulty and impossibility. Choice C is correct because it accurately states that NP-complete problems have algorithms that eventually solve every instance, even though the time required may be impractically large for big inputs. Choice A is incorrect as it claims NP-complete problems have no algorithms at all, which would make them undecidable. To help students: Use concrete examples to show that brute-force algorithms exist for NP-complete problems. Emphasize that 'hard to solve efficiently' is very different from 'impossible to solve algorithmically'.
In the passage’s Halting Problem example, what question did the algorithm attempt to answer about a program?
Whether the program produced the correct output, since correctness and halting were the same property.
Whether the program used recursion, since recursion was the main cause of non-terminating behavior.
Whether the program ran in polynomial time, since efficiency determined whether it could be decided.
Whether the program eventually stopped or ran forever on a given input, for every possible program.
Explanation
This question tests understanding of undecidable problems in algorithms and programming (AP CSP). The Halting Problem specifically asks whether a program will eventually stop (halt) or continue running forever when given a particular input. The passage uses this as the classic example of an undecidable problem. Choice B is correct because it precisely states what the Halting Problem asks - whether a program stops or runs forever on a given input, and this must be determined for any possible program. Choice D is incorrect as halting and correctness are different properties; a program can halt with incorrect output or run forever while producing partial correct results. To help students: Use simple program examples with loops to illustrate halting vs non-halting behavior. Emphasize that the challenge is creating one algorithm that can analyze any arbitrary program.
Which of the following best explained why the Halting Problem was undecidable, based on the passage’s definition?
Because no algorithm could correctly decide halting for every program-input pair, even with unlimited time.
Because it was NP-complete, so no efficient algorithm existed even though a slow one always worked.
Because it required infinite memory to store all possible programs before making any decision at all.
Because some programs always crashed, and crashes made the question meaningless for computability.
Explanation
This question tests understanding of undecidable problems in algorithms and programming (AP CSP). The Halting Problem is undecidable because it's mathematically proven that no algorithm can correctly determine halting behavior for every possible program-input combination. The passage emphasizes this fundamental impossibility. Choice D is correct because it captures the essence of undecidability - no algorithm exists that can always give the right answer for every program-input pair, regardless of available time or resources. Choice B is incorrect as it confuses undecidability with NP-completeness; the Halting Problem doesn't have even a slow algorithm that works for all cases. To help students: Walk through the diagonalization proof that shows why a universal halting detector leads to contradiction. Emphasize that this is a mathematical impossibility, not a practical limitation.
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 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.
Undecidable problems had no correct answers, while NP-complete problems always had one answer.
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 were solved by heuristics, while NP-complete problems were solved instantly by compilers.
Undecidable problems lacked any always-correct terminating algorithm, while NP-complete problems still had one.
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.