Namespaces
Variants
Actions

Difference between revisions of "Decision problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
(TeX done)
 
Line 1: Line 1:
 
''algorithmic problem''
 
''algorithmic problem''
  
The question of the existence of an effective computational procedure or [[Algorithm|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.
+
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.
 
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|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|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.
+
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|Algorithmic problem]].
+
Cf. also [[Algorithmic problem]].
  
  
Line 16: Line 16:
 
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.
 
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 problemHilbert's 10-th problem" ); 3) the problem of deciding for any well-formed formula from the first-order predicate calculus whether or not that formula is valid (the  "EntscheidungsproblemEntscheidungsproblem" ); 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 problemword problem"  for groups).
+
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.  
  
The term  "mass problemmass problem" , the literal translation of the original title of this article, rarely occurs in the literature.
+
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====
 
====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Davis,  "Computability and unsolvability" , McGraw-Hill  (1958)</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  M. Davis (ed.) , ''The undecidable'' , Raven Press  (1965)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  H. Hermes,  "Enumerability, decidability, computability" , Springer  (1965)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  M. Minsky,  "Computation: finite and infinite machines" , Prentice-Hall  (1972)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR></table>
+
<table>
 +
<TR><TD valign="top">[a1]</TD> <TD valign="top">  M. Davis,  "Computability and unsolvability" , McGraw-Hill  (1958)</TD></TR>
 +
<TR><TD valign="top">[a2]</TD> <TD valign="top">  M. Davis (ed.) , ''The undecidable'' , Raven Press  (1965)</TD></TR>
 +
<TR><TD valign="top">[a3]</TD> <TD valign="top">  H. Hermes,  "Enumerability, decidability, computability" , Springer  (1965)</TD></TR>
 +
<TR><TD valign="top">[a4]</TD> <TD valign="top">  M. Minsky,  "Computation: finite and infinite machines" , Prentice-Hall  (1972)</TD></TR>
 +
<TR><TD valign="top">[a5]</TD> <TD valign="top">  H. Rogers jr.,  "Theory of recursive functions and effective computability" , McGraw-Hill  (1967)  pp. 164–165</TD></TR>
 +
</table>
 +
 
 +
{{TEX|done}}

Latest revision as of 22:33, 10 January 2016

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
How to Cite This Entry:
Decision problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Decision_problem&oldid=16725
This article was adapted from an original article by S.I. Adyan (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article