Advanced Placement (AP) Computer Science

What characterizes a problem as undecidable?

1. An algorithm can solve it in a finite amount of time

2. The problem can only be solved with brute force

3. It cannot be determined if a solution exists for all inputs

4. The problem can be solved with a deterministic algorithm

The correct answer is: It cannot be determined if a solution exists for all inputs

A problem is characterized as undecidable when it cannot be determined whether a solution exists for all possible inputs. This means that there is no algorithm that can universally conclude whether a given input will have a solution or not, regardless of the complexity or nature of that input. Undecidable problems arise in theoretical computer science, typically in the context of decision problems, where the algorithm must produce a yes or no answer based on whether a solution fits a given criteria. For example, the Halting Problem is a well-known undecidable problem, which illustrates that there is no algorithm that can determine, for every possible program-input pair, whether the program will eventually halt (finish executing) or run forever. The other options do not accurately define undecidability. An algorithm that can solve a problem in a finite amount of time implies that the problem is decidable; brute force techniques can sometimes address decidable problems by exhaustively checking all possible cases; deterministic algorithms, which provide a predictable output for a given input, also pertain to decidable problems. Therefore, the essential characteristic of undecidability lies in the inability to ascertain the existence of solutions across all inputs.