Decision problem

algorithmic problem

The question of the existence of an effective computational procedure or algorithm for deciding the truth of falsity of any instance of a parametric statement. Simple examples of decision problems are: addition of two given decimal numbers, multiplication of two given numbers, the verification of whether or not a given integer is prime, to find the derivative of a given function, to expand a given function into a power series, etc.

If no algorithm exists for a problem at hand, this problem is said to be undecidable or unsolvable.

The problem of finding an algorithm which solves a given decision problem is sometimes also called the recognition problem or solvability problem. This last somewhat unfortunate term historically first appeared in connection with the problem of deciding for a well-formed formula from the first-order predicate calculus whether the formula is valid. Generally speaking, when considering the solvability of a given decision problem it is natural to consider this problem in terms of the existence or non-existence of an algorithm for it.

Cf. also Algorithmic problem.

Comments

Decision problems are meaningful only when the notion of an effective computational procedure is suitably formalized, as in the theory of algorithms.

A positive solution to a decision problem consists of giving an algorithm for solving it, the problem is then said to be decidable or solvable.

Examples of solvable decision problems are: i) the problem of deciding whether or not a given integer is prime; and ii) the problem of deciding for any polynomial with integer coefficients whether or not it has a real root.

Examples of unsolvable decision problems are: 1) the problem of deciding for any effectively given real number whether or not it is zero; 2) the problem of deciding for any multi-variable polynomial with integer coefficients whether or not that polynomial has all integer roots ( "Hilbert 10th problem", cf. Hilbert problems); 3) the problem of deciding for any well-formed formula from the first-order predicate calculus whether or not that formula is valid (the "Entscheidungsproblem" ); and 4) the problem of deciding for any group given in terms of generators and relations and any string of generators whether or not that string can be reduced to the identity in the group (the "word problem" for groups).

The term "mass problem" , the literal translation of the original title of this article, rarely occurs in the literature.

References

[a1]	M. Davis, "Computability and unsolvability" , McGraw-Hill (1958)
[a2]	M. Davis (ed.) , The undecidable , Raven Press (1965)
[a3]	H. Hermes, "Enumerability, decidability, computability" , Springer (1965)
[a4]	M. Minsky, "Computation: finite and infinite machines" , Prentice-Hall (1972)
[a5]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165