In logic, a **decision problem** is determining whether or not there exists a **decision procedure** or algorithm for a class S of questions requiring a Boolean value (i.e., a *true* or *false*, or *yes* or *no*). These are also known as yes-or-no questions. For example, the decision problem for the class of questions "Does *x* divide *y* without remainder?" is *decidable* because there exists a mechanical procedure, namely long division, which allows us to determine for any *x* and any *y* whether the answer for "Does *x* divide *y* without remainder?" is *yes* or *no*.

Every decision problem is reducible to a computation problem in the following way. Every class of yes-or-no questions is reducible to the predicate form "Is *P*(*x*_{1},...,*x*_{n}) true?". For example, the above example is reducible to "Is *P*(*x*,*y*) true?". This predicate form is reducible to the representing function

So deciding whether *P*(*x*_{1},...,*x*_{n}) is true is equivalent to computing the value for *f*(*x*_{1},...,*x*_{n}).

## Definition

A **decision problem** is a countable set *S* and a function

- .

Let *A* be the preimage of *f* for 0.

The problem is called **decidable** if *A* is a recursive set. It is called **partially decidable**, **solvable** or **provable** if *A* is a recursively enumerable set. Otherwise the problem is called **undecidable**.

We can give an alternative definition in terms of computable functions:

If *f* is a total computable function the problem is called **computable**. If *f* is only a partial computable function the problem is called **partially computable**. Otherwise the problem is called **uncomputable**.

## Notes

It should be noted that a decision problem is always a set of related problems which is in some sense large enough. A single problem *P* is always trivially decidable by assigning the constant function *f*(*P*)≡0 or *f*(*P*)≡1 to it.

Nearly every problem can be cast as a decision problem by using reductions, often with little effect on the amount of time or space needed to solve the problem. Many traditional hard problems have been cast as decision problems because this makes them easier to study and to solve, and proving that these problems are hard suffices to show that more complex problems are hard as well.

## Examples

Important undecidable decision problems include the halting problem and Goodstein's theorem; for more, see list of undecidable problems. In computational complexity, decision problems which are complete are used to characterize complexity classes of decision problems. Important examples include the boolean satisfiability problem and several of its variants, along with the undirected and directed reachability problem .

Last updated: 05-13-2005 07:56:04