Information about Decision Procedure
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. 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.
Methods used to solve decision problems are called decision procedures or algorithms. An algorithm for the decision problem "given two numbers x and y, does x evenly divide y?" would explain how to determine whether x evenly divides y, given x and y. One such algorithm is taught to all school children and is called "long division." A decision problem which can be solved by some 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.
Formally, a decision problem is a subset A of the natural numbers. By using Gödel numbers, it is possible to study other sets such as formal languages. The informal "problem" is that of deciding whether a given number is in the set.
A decision problem is called decidable or effectively solvable if A is a recursive set. A problem is called partially decidable, semidecidable, solvable, or provable if A is a recursively enumerable set. Partially decidable problems and any other problems that are not decidable are called undecidable.
Important undecidable decision problems include the halting problem; for more, see list of undecidable problems. In computational complexity, decision problems which are complete are used to characterize complexity classes of decision problems. Important examples include the boolean satisfiability problem and several of its variants, along with the undirected and directed reachability problem.
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) = 2x has this property.
Every decision problem can be converted into the function problem of computing the 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 is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.
..... Click the link for more information.
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.
Methods used to solve decision problems are called decision procedures or algorithms. An algorithm for the decision problem "given two numbers x and y, does x evenly divide y?" would explain how to determine whether x evenly divides y, given x and y. One such algorithm is taught to all school children and is called "long division." A decision problem which can be solved by some 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.
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 in terms of the set of inputs for which the problem returns yes. In this sense, a decision problem is equivalent to a formal language.Formally, a decision problem is a subset A of the natural numbers. By using Gödel numbers, it is possible to study other sets such as formal languages. The informal "problem" is that of deciding whether a given number is in the set.
A decision problem is called decidable or effectively solvable if A is a recursive set. A problem is called partially decidable, semidecidable, solvable, or provable if A is a recursively enumerable set. Partially decidable problems and any other problems that are not decidable are called undecidable.
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 methods of primality testing are known, the existence of any effective method is enough to establish decidability.Important undecidable decision problems include the halting problem; for more, see list of undecidable problems. In computational complexity, decision problems which are complete are used to characterize complexity classes of decision problems. Important examples include the boolean satisfiability problem and several of its variants, along with the undirected and directed reachability problem.
History
The Entscheidungsproblem, German for "Decision-problem", is attributed to David Hilbert: "At [the] 1928 conference Hilbert made his questions quite precise. First, was mathematics complete... Second, was mathematics consistent... And thirdly, was mathematics decidable? By this he meant, did there exist a definite method which could, in principle be applied to any assertion, and which was guaranteed to produce a correct decision on whether that assertion was true" (Hodges, p. 91). Hilbert believed that "in mathematics there is no ignorabimus' (Hodges, p. 91ff) meaning 'we will not know'. See David Hilbert and Halting Problem for more.Equivalence with function problems
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) = 2x has this property.
Every decision problem can be converted into the function problem of computing the 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 is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.
References
- Hanika, Jiri. Search Problems and Bounded Arithmetic. PhD Thesis, Charles University, Prague. http://eccc.hpi-web.de/pub/eccc/theses/hanika.pdf.
- Hodges, A., Alan Turing: The Enigma, Simon and Schuster, New York. Cf Chapter "The Spirit of Truth" for some more history that led to Turing's work.
- :Hodges references a biography of David Hilbert: Constance Reid, Hilbert (George Allen & Unwin; Springer-Verlag, 1970). There are apparently more recent editions.
- Kozen, D.C. (1997), Automata and Computability, Springer.
- Hartley Rogers, Jr., The Theory of Recursive Functions and Effective Computability, MIT Press, ISBN 0-262-68052-1 (paperback), ISBN 0-07-053522-1
- Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co.
- Robert I. Soare (1987), Recursively Enumerable Sets and Degrees, Springer-Verlag, ISBN 0-387-15299-7
Computability theory may refer to:
..... Click the link for more information.
- Recursion theory, a branch of mathematical logic, contemporarily called computability theory.
- Computability theory (computer science), locating basic questions of what is computable within the context of theoretical computer science.
..... Click the link for more information.
As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g.
..... Click the link for more information.
..... Click the link for more information.
This article or section is in need of attention from an expert on the subject.
Please help recruit one or [ improve this article] yourself. See the talk page for details.
..... Click the link for more information.
Please help recruit one or [ improve this article] yourself. See the talk page for details.
..... Click the link for more information.
In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO.
..... Click the link for more information.
..... Click the link for more information.
In computer science, an optimization problem is the problem of finding the best solution from all feasible solutions. More formally, an optimization problem is a quadruple , where
..... Click the link for more information.
- is a set of instances;
- given an instance , is the set of feasible solutions;
..... Click the link for more information.
In mathematics, computing, linguistics, and related disciplines, an algorithm is a finite list of well-defined instructions for accomplishing some task that, given an initial state, will proceed through a well-defined series of successive states, eventually terminating in an
..... Click the link for more information.
..... Click the link for more information.
In computational complexity theory, a computational resource is a resource used by some computational models in the solution of computational problems.
The simplest computational resources are computation time, the number of steps necessary to solve a problem, and
..... Click the link for more information.
The simplest computational resources are computation time, the number of steps necessary to solve a problem, and
..... Click the link for more information.
Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability and definability.
..... Click the link for more information.
..... Click the link for more information.
Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic unsolvability of the set. The concept of Turing degree is fundamental in computability theory, where sets of natural numbers are often regarded as decision problems; the
..... Click the link for more information.
..... Click the link for more information.
- This article is about the term formal language as it is used in mathematics, logic and computer science. For information about a mode of expression that is more disciplined or precise than everyday speech, see Register (linguistics).
..... Click the link for more information.
Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number called its Gödel number. The concept was first used by Kurt Gödel for the proof of his incompleteness theorem.
..... Click the link for more information.
..... Click the link for more information.
In computability theory, a set of natural numbers is called recursive, computable or decidable if there is an algorithm which terminates after a finite amount of time and correctly decides whether or not a given number belongs to the set.
..... Click the link for more information.
..... Click the link for more information.
recursively enumerable, computably enumerable, semidecidable or provable if:
..... Click the link for more information.
- There is an algorithm that, when given an input number, eventually halts if and only if the input is an element of S.
..... Click the link for more information.
A primality test is an algorithm for determining whether an input number is prime. It is important to note the difference between primality testing and integer factorization.
..... Click the link for more information.
..... Click the link for more information.
In computability theory the halting problem is a decision problem which can be stated as follows:
..... Click the link for more information.
- Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input.
..... Click the link for more information.
In computability theory, an undecidable problem is a problem whose language is not a recursive set. More informally, such problems cannot be solved in general by computers; see decidability. This is a list of undecidable problems.
..... Click the link for more information.
..... Click the link for more information.
As a branch of the theory of computation in computer science, computational complexity theory investigates the problems related to the amounts of resources required for the execution of algorithms (e.g.
..... Click the link for more information.
..... Click the link for more information.
In computational complexity theory, a computational problem is complete for a complexity class when it is, in a formal sense, one of the "hardest" or "most expressive" problems in the complexity class.
..... Click the link for more information.
..... Click the link for more information.
Satisfiability is the problem of determining if the variables of a given boolean formula can be assigned in such a way as to make the formula evaluate to TRUE. Equally important is to determine whether no such assignments exist, which would imply that the function expressed by the
..... Click the link for more information.
..... Click the link for more information.
In computational complexity theory, SL (Symmetric Logspace or Sym-L) is the complexity class of problems log-space reducible to USTCON (undirected s-t connectivity
..... Click the link for more information.
..... Click the link for more information.
In mathematics, the Entscheidungsproblem (German for 'decision problem') is a challenge posed by David Hilbert in 1928.
The Entscheidungsproblem asks for a computer program that will take as input a description of a formal language and a mathematical statement in the
..... Click the link for more information.
The Entscheidungsproblem asks for a computer program that will take as input a description of a formal language and a mathematical statement in the
..... Click the link for more information.
David Hilbert
David Hilbert (1912)
Born January 23 1862
Wehlau (Welawa), Province of Prussia
..... Click the link for more information.
David Hilbert (1912)
Born January 23 1862
Wehlau (Welawa), Province of Prussia
..... Click the link for more information.
The ignorabimus, short for the Latin maxim ignoramus et ignorabimus meaning "we do not know and will not know", stood for a pessimistic (in one sense) position on the limits of scientific knowledge, in the thought of the nineteenth century.
..... Click the link for more information.
..... Click the link for more information.
David Hilbert
David Hilbert (1912)
Born January 23 1862
Wehlau (Welawa), Province of Prussia
..... Click the link for more information.
David Hilbert (1912)
Born January 23 1862
Wehlau (Welawa), Province of Prussia
..... Click the link for more information.
In computability theory the halting problem is a decision problem which can be stated as follows:
..... Click the link for more information.
- Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input.
..... Click the link for more information.
In computational complexity theory, a function problem is a problem other than a decision problem, that is, a problem requiring a more complex answer than just YES or NO.
..... Click the link for more information.
..... Click the link for more information.
indicator function or a characteristic function is a function defined on a set that indicates membership of an element in a subset of .
The indicator function of a subset of a set is a function
defined as
..... Click the link for more information.
The indicator function of a subset of a set is a function
defined as
..... Click the link for more information.
David Hilbert
David Hilbert (1912)
Born January 23 1862
Wehlau (Welawa), Province of Prussia
..... Click the link for more information.
David Hilbert (1912)
Born January 23 1862
Wehlau (Welawa), Province of Prussia
..... Click the link for more information.
Constance Bowman Reid is the author of several biographies of mathematicians and popular books about mathematics.
She is the sister of mathematician Julia Robinson.
..... Click the link for more information.
She is the sister of mathematician Julia Robinson.
Publications
- From zero to infinity. What makes numbers interesting. Fifth edition.
..... Click the link for more information.
This article is copied from an article on Wikipedia.org - the free encyclopedia created and edited by online user community. The text was not checked or edited by anyone on our staff. Although the vast majority of the wikipedia encyclopedia articles provide accurate and timely information please do not assume the accuracy of any particular article. This article is distributed under the terms of GNU Free Documentation License.
Herod_Archelaus
