Decision problem

related topics
{math, number, function}
{law, state, case}
{work, book, publish}
{school, student, university}

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem. The answer can be either 'yes' or 'no', and depends upon the values of x and y.

Decision problems are closely related to function problems, 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?". They are also related to optimization problems, which are concerned with finding the best answer to a particular problem.

A method for solving a decision problem given in the form of an algorithm is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers x and y, does x evenly divide y?" would give the steps for determining whether x evenly divides y, given x and y. One such algorithm is long division, taught to many school children. If the remainder is zero the answer produced is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm, such as this example, is called decidable.

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

Research in computability theory has typically focused on decision problems. As explained in the section Equivalence with function problems below, there is no loss of generality.

Contents

Definition

A decision problem is any arbitrary yes-or-no question on an infinite set of inputs. Because of this, it is traditional to define the decision problem equivalently as: the set of inputs for which the problem returns yes.

These inputs can be natural numbers, but also other values of some other kind, such as strings of a formal language. Using some encoding, such as Gödel numberings, the strings can be encoded as natural numbers. Thus, a decision problem informally phrased in terms of a formal language is also equivalent to a set of natural numbers. To keep the formal definition simple, it is phrased in terms of subsets of the natural numbers.

Full article ▸

related documents
Euler's criterion
Partial fractions in integration
BPP
Alternative algebra
NP-hard
Regular space
Real line
Intersection (set theory)
C*-algebra
Polynomial time
Bézout's identity
Heaviside step function
Algebraic number
T1 space
Whittaker–Shannon interpolation formula
CLU (programming language)
Stirling number
Magma (algebra)
Dyadic rational
Separated sets
Cayley's theorem
Twin prime conjecture
Syntactic sugar
Magma computer algebra system
Topological ring
Goldbach's weak conjecture
Kernel (category theory)
Category (mathematics)
Subalgebra
Amicable number