Decision problem

A decision problem is a specific type of computational question. Every input for a decision problem results in one of two possible outputs: YES or NO.

These problems use a set of input values to seek a binary answer. The inputs can be natural numbers or other types of data. They might be binary strings or strings from a different alphabet. In formal language, a decision problem is the set of all inputs that produce a YES answer. If every input is encoded by an alphabet, the problem is a subset of that alphabet. You can even use Gödel numbering to turn any string into a natural number. This allows any decision problem to be defined as a subset of natural numbers.

To solve these problems, we use a decision procedure. This is an algorithmic method that provides the correct YES or NO answer for every input. If such a procedure exists, the decision problem is called decidable. A problem is also called effectively solvable if the set of YES inputs is a recursive set. For example, asking if one number x evenly divides another number y is a decidable problem. You can use long division as a decision procedure to find the answer. Another classic example is determining if a natural number is prime. You can decide this by testing every possible nontrivial factor. Even if a faster method exists, the ability to test factors proves it is decidable.

Not all problems can be solved by an algorithm. If no decision procedure can ever be created, the problem is undecidable. This means it is impossible to solve the problem, no matter how much time or power you have. The halting problem is one of the most famous undecidable problems in mathematics. Some problems are also called partially decidable or semidecidable. These occur when the set of YES inputs is a recursively enumerable set. For these problems, you might find a YES answer, but you cannot always confirm a NO answer. To study these unsolvable tasks, researchers use recursion theory. This field categorizes undecidable problems by their Turing degree, which measures their inherent noncomputability.

Computer scientists also group decidable problems by their difficulty. This is the focus of computational complexity theory. Difficulty is measured by the computational resources required by the most efficient algorithm. Some problems are more central to their groups than others. We call a problem "complete" if it belongs to a specific set and can represent every other problem in that set. This is done through processes like many-one reducibility or polynomial-time reductions. For instance, the Boolean satisfiability problem is complete for the class NP. Using complete problems helps scientists characterize entire classes of complexity.

Decision problems are closely linked to function problems. While decision problems only give YES or NO, function problems have more complex answers. A function problem asks for a specific value, such as asking what x divided by y equals. Every function problem can be transformed into a decision problem. You can do this by looking at the graph of the function. The graph is the set of all pairs (x, y) where the function f(x) equals y. If this new decision problem is effectively solvable, the original function problem is also solvable. However, this transformation does not always preserve the same level of computational complexity.

Another related area is optimization problems. These do not look for a simple YES or NO, but rather the best possible answer. Examples include the traveling salesman problem or questions in linear programming. In the traveling salesman problem, the goal is to find a tour with minimal weight. You can turn this optimization task into a decision problem to make it easier to study. You might ask if a graph has any tour with a weight less than a specific number N. By repeatedly answering this decision question, you can eventually find the minimal weight. This allows researchers to use the well-developed theory of decision problems to solve complex real-world tasks.

In summary, decision problems serve as the foundation for much of modern computational theory. They allow us to map the boundaries between what is possible and what is impossible. By converting complex functions and optimization tasks into simple YES or NO questions, we can measure exactly how much work a computer must do. Whether we are studying the limits of logic through undecidability or the speed of algorithms through complexity, decision problems provide the essential framework for understanding computation.