Editing Decision problem (section)

{{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.