Editing Decision problem

{{short description|Yes/no problem in computer science}}
{{about|decision problems in complexity theory|the decision problem in formal logic|Entscheidungsproblem|analysis of the process of making choices|Decision theory}}
[[Image:Decision Problem.svg|thumb|200px|A ''decision problem'' has only two possible outputs (''YES'' or ''NO'') on any input.]]

In [[computability theory]] and [[computational complexity theory]], a '''decision problem''' is a [[computational problem]] that can be posed as a [[yes–no question]] on a [[set (mathematics)|set]] of input values. An example of a decision problem is deciding whether a given natural number is [[Prime number|prime]]. Another example is the problem, "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?"

A '''decision procedure''' for a decision problem is an [[algorithm|algorithmic]] method that answers the yes-no question on all inputs, and a decision problem is called '''[[decidability (logic)|decidable]]''' if there is a decision procedure for it.  For example, the decision problem "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?" is decidable since there is a decision procedure called [[long division]] that gives the steps for determining whether ''x'' evenly divides ''y'' and the correct answer, ''YES'' or ''NO'', accordingly. Some of the most important problems in mathematics are '''[[undecidable problem|undecidable]]''', e.g. the [[halting problem]].

The field of computational complexity theory categorizes ''decidable'' decision problems by how difficult they are to solve. "Difficult", in this sense, is described in terms of the [[computational resource]]s needed by the most efficient algorithm for a certain problem. On the other hand, the field of [[recursion theory]] categorizes ''undecidable'' decision problems by [[Turing degree]], which is a measure of the noncomputability inherent in any solution.

==Definition==
A ''decision problem'' is the [[formal language]] of all inputs for which the output (the answer to the yes-no question on a given input) is ''YES''.<ref group="notes" name="def"/>

* These inputs can be natural numbers, but can also be values of some other kind, like binary [[string (computer science)|string]]s or strings over some other [[Alphabet (computer science)|alphabet]].

* For example, if every input can be encoded by the alphabet <math>\{0,1\}</math>, then a decision problem is a subset <math>L\subseteq\{0,1\}^*</math>.<ref group="notes" name="def"/>

* For another example, using an encoding such as [[Gödel numbering]], any string can be encoded as a natural number, via which a decision problem can be defined as a subset of the natural numbers. Therefore, the decision procedure of a decision problem is to compute the [[Indicator function|characteristic function]] of a subset of the natural numbers.

==Examples==
A classic example of a decidable decision problem is the set of prime numbers. It is possible to effectively decide whether a given natural number is prime by testing every possible nontrivial factor. Although much more efficient procedures of [[primality testing]] are known, the existence of any effective procedure is enough to establish decidability.

== Decidability ==

{{main|Undecidable problem|Decidability (logic)}}

* A decision problem is ''decidable'' or ''effectively solvable'' if the set of inputs for which the answer is ''YES'' is a [[recursive set]].<ref group="notes" name="rec-set"/>
* A decision problem is ''partially decidable'', ''semidecidable'', ''solvable'', or ''provable'' if the set of inputs for which the answer is ''YES'' is a [[recursively enumerable set]].

Problems that are not decidable are ''undecidable'', which means it is not possible to create an algorithm (efficient or not) that solves them. The [[halting problem]] is an important undecidable decision problem; for more examples, see [[list of undecidable problems]].

== Complete problems ==

{{main|Complete problem}}

Decision problems can be ordered according to [[many-one reduction|many-one reducibility]] and related to feasible reductions such as [[polynomial-time reduction]]s. A decision problem ''P'' is said to be ''[[complete problem|complete]]'' for a set of decision problems ''S'' if ''P'' is a member of ''S'' and every problem in ''S'' can be reduced to ''P''. Complete decision problems are used in [[computational complexity theory]] to characterize [[complexity class]]es of decision problems. For example, the [[Boolean satisfiability problem]] is complete for the class [[NP (complexity)|NP]] of decision problems under polynomial-time reducibility.

==Function problems==
{{main|Function problem}}

Decision problems are closely related to [[function problem]]s, which can have answers that are more complex than a simple ''YES'' or ''NO''.  A corresponding function problem is "given two numbers ''x'' and ''y'', what is ''x'' divided by ''y''?".

A [[function problem]] consists of a [[partial function]] ''f''; the informal "problem" is to compute the values of ''f'' on the inputs for which it is defined.

Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function.   (The graph of a function ''f'' is the set of pairs (''x'',''y'') such that ''f''(''x'') = ''y''.)  If this decision problem were effectively solvable then the function problem would be as well.  This reduction does not respect computational complexity, however.  For example, it is possible for the graph of a function to be decidable in polynomial time (in which case running time is computed as a function of the pair (''x'',''y'')) when the function is not computable in [[polynomial time]] (in which case running time is computed as a function of ''x'' alone).  The function ''f''(''x'') = 2<sup>''x''</sup> has this property.

Every decision problem can be converted into the function problem of computing the [[indicator function|characteristic function]] of the set associated to the decision problem.   If this function is computable then the associated decision problem is decidable. However, this reduction is more liberal than the standard reduction used in computational complexity (sometimes called polynomial-time many-one reduction); for example, the complexity of the characteristic functions of an [[NP-complete]] problem and its [[co-NP-complete]] [[Complement (complexity)|complement]] is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.

==Optimization problems==
{{main|Optimization problem}}

Unlike decision problems, for which there is only one correct answer for each input, optimization problems are concerned with finding the ''best'' answer to a particular input.  Optimization problems arise naturally in many applications, such as the [[traveling salesman problem]] and many questions in [[linear programming]].

Function and optimization problems are often transformed into decision problems by considering the question of whether the output is ''equal to'' or ''less than or equal to'' a given value. This allows the complexity of the corresponding decision problem to be studied; and in many cases the original function or optimization problem can be solved by solving its corresponding decision problem. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each ''N'', to decide whether the graph has any tour with weight less than ''N''.  By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour.

Because the theory of decision problems is very well developed, research in complexity theory has typically focused on decision problems. Optimization problems themselves are still of interest in computability theory, as well as in fields such as [[operations research]].

== See also ==
* [[ALL (complexity)]]
* [[Computational problem]]
* [[Counting problem (complexity)]]
* [[Decidability (logic)]] &ndash; for the problem of deciding whether a formula is a consequence of a [[logical theory]].
* [[Formal language]]
* [[Search problem]]
* [[Word problem (mathematics)]]

== Notes ==
{{reflist|group=notes|refs=
<ref name="def">{{cite web|url=https://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf |archive-url=https://web.archive.org/web/20151010023326/http://www.cs.stanford.edu/~trevisan/cs254-10/lecture02.pdf |archive-date=2015-10-10 |url-status=live|title=CS254: Computational Complexity: Handout 2}}</ref>
<ref name="rec-set">This conclusion follows the [[recursive set#Properties|properties of recursive set]], which states that the set of inputs for which the answer is ''NO'' is also recursive.</ref>
}}

== References ==
*{{cite book |first=D.C. |last=Kozen |title=Automata and Computability |publisher=Springer |date=2012 |isbn=978-1-4612-1844-9 |url=https://books.google.com/books?id=Vo3fBwAAQBAJ&q=%22decision+problem%22}}
*{{cite book |first=Rogers Jr |last=Hartley  |title=The Theory of Recursive Functions and Effective Computability |publisher=MIT Press |date=1987 |isbn=978-0-262-68052-3 }}
*{{cite book  |author-link=Michael Sipser |first=M. |last=Sipser |title=Introduction to the Theory of Computation |publisher=Cengage Learning |date=2020 |isbn=978-0-357-67058-3 }}
*{{cite book |first=Robert I. |last=Soare |title=Recursively Enumerable Sets and Degrees |publisher=Springer |date=1987 |isbn=0-387-15299-7 |url=https://books.google.com/books?id=9I7Pl00LU5gC&pg=PP1}}
*{{cite book |author-link=Daniel Kroening |first1=Daniel |last1=Kroening |first2=Ofer |last2=Strichman |author2-link=Ofer Strichman |title=Decision procedures |publisher=Springer |date= 23 May 2008|isbn=978-3-540-74104-6 |url=https://books.google.com/books?id=SaUywbXY9C8C&pg=PR1}}
*{{cite book |first1=Aaron |last1=Bradley |author2-link=Zohar Manna |first2=Zohar |last2=Manna |title=The calculus of computation |publisher=Springer |date= 3 September 2007|isbn=978-3-540-74112-1 |url=https://books.google.com/books?id=0MbX7xVpffAC&pg=PR2}}

{{Mathematical logic}}
{{Authority control}}

[[Category:Computational problems]]
[[Category:Computability theory]]