| Decision Problem |
Article Index for Decision |
Website Links For Decision |
Information AboutDecision Problem |
| CATEGORIES ABOUT DECISION PROBLEM | |
| logic | |
| theory of computation | |
| computational problems | |
| recursion theory | |
|
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 Problem s, which are concerned with finding the ''best'' answer to a particular problem. Methods used to solve decision problems are called ''decision procedures'' or Algorithm s. 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 Resource s 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 Number s, 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 ''' (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'') = ''2''''x'' 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
::Hodges references a biography of , ''Hilbert'' (George Allen & Unwin; Springer-Verlag, 1970). There are apparently more recent editions.
|
|
|