Can every question be answered by a machine? The logic of decision problems
In short: A decision problem is any question that demands a simple yes or no answer for a given input. While some are easily solved by algorithms, others are fundamentally undecidable. Understanding these boundaries reveals the limits of computation and how we categorize the difficulty of the world's most complex puzzles.
At its core, a decision problem is a computational task where the output is strictly binary: yes or no. Whether you are checking if a number is prime or determining if one integer evenly divides another, you are engaging with a decision problem. If an algorithmic procedure exists that can reliably provide the correct answer for every possible input, the problem is classified as decidable. For instance, long division serves as a decision procedure for divisibility, and testing factors confirms primality.
However, not all problems share this fate. Some, like the famous halting problem, are undecidable, meaning no algorithm can ever be constructed to solve them. In these cases, it is impossible to create a universal method that yields a definitive answer. Researchers categorize these undecidable challenges using Turing degrees, which measure the inherent noncomputability of a problem. Conversely, for decidable problems, computational complexity theory focuses on efficiency, measuring the resources required by the most effective algorithm to reach a solution.
Decision problems are foundational to broader mathematical inquiry. They are often linked to function problems—where the answer is more complex than a binary choice—and optimization problems, which seek the best possible outcome. By transforming an optimization task, such as finding the shortest path in a network, into a series of yes-no questions about whether a solution exists below a certain threshold, mathematicians can apply the well-developed tools of decision theory to solve them. This framework allows researchers to classify problems by their difficulty, such as identifying those that are complete for specific complexity classes, like the Boolean satisfiability problem for the class NP.
Ultimately, the study of these problems defines the limits of what computers can achieve. Whether a problem is recursive, recursively enumerable, or entirely beyond algorithmic reach, the classification of decision problems provides a rigorous map of the logical landscape, separating the solvable from the permanently out of reach.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Decision problem
- Also: Decision problem | Optimization, Algorithms & Complexity | Britannica
To cite this card, link to https://intellectplus.co.uk/app/science-decision-problem.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?