(definition)

**Definition:**
A problem with a "yes" or "no" answer. Equivalently, a *function* whose *range* is two values, such as {0,1}.

**See also**
*optimization problem*, *certificate*, *NP*, *NP-complete*.

*Note:
A decision problem asks, is there a solution with a certain characteristic? An optimization problem asks, what is the best solution? For instance, the traveling salesman problem is an optimization problem, while the corresponding decision problem asks if there is a Hamiltonian cycle with a cost less than some fixed amount k. *

* From Algorithms and Theory of Computation Handbook, page 26-20, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.*

Author: CRC-A

History, definitions, examples, etc. given in Comp.Theory FAQ, scroll down to **P vs. NP**.

Go to the Dictionary of Algorithms and Data Structures home page.

If you have suggestions, corrections, or comments, please get in touch with Paul Black.

Entry modified 5 September 2012.

HTML page formatted Fri Feb 23 10:06:07 2018.

Cite this as:

Algorithms and Theory of Computation Handbook, CRC Press LLC, 1999, "decision problem", in
*Dictionary of Algorithms and Data Structures* [online], Vreda Pieterse and Paul E. Black, eds. 5 September 2012. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/decisionProblem.html