FACTOID # 27: If you're itching to live in a trailer park, hitch up your home and head to South Carolina, where a whopping 18% of residences are mobile homes.
 
 Home   Encyclopedia   Statistics   States A-Z   Flags   Maps   FAQ   About 
   
 
WHAT'S NEW
 

SEARCH ALL

FACTS & STATISTICS    Advanced view

Search encyclopedia, statistics and forums:

 

 

(* = Graphable)

 

 


Encyclopedia > Decision problem

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. Computability theory is the branch of theoretical computer science that studies which problems are computationally solvable using different models of computation. ... As a branch of the theory of computation in computer science, computational complexity theory describes the scalability of algorithms, and the inherent difficulty in providing scalable algorithms for specific computational problems. ... In logic, mathematics, and computer science, a formal system is a formal grammar used for modelling purposes. ...


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. 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. Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization problem... In computer science, an optimization problem is the problem to find among all feasible solutions for some problem the best one. ...


Methods used to solve decision problems are called decision procedures or algorithms. An algorithm for this decision problem would explain how to determine whether x evenly divides y, given x and y. A decision problem which can be solved by some algorithm is called decidable. In mathematics, computing, linguistics, and related disciplines, an algorithm is a procedure (a finite set of well-defined instructions) for accomplishing some task which, given an initial state, will terminate in a defined end-state. ...


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. In computational complexity theory, a computational resource is a resource used by some computational model in the solution of computational problems. ... Recursion theory, or computability theory, is a branch of mathematical logic dealing with generalizations of the notion of computable function, and with related notions such as Turing degrees and effective descriptive set theory. ... In computability theory, the Turing degree of a subset of the natural numbers, , is the equivalence class of all subsets of equivalent to under Turing reducibility. ...


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. In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer. ...

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 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. In mathematics, logic, and computer science, a formal language is a set of finite-length words (i. ...


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. This article or section may be confusing or unclear for some readers, and should be edited to rectify this. ...


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. Otherwise, the problem is called undecidable. In computability theory a countable set is called recursive, computable or decidable if we can construct an algorithm which terminates after a finite amount of time and decides whether or not a given element belongs to the set. ... In computability theory, traditionally called recursion theory, a set S of natural numbers is called recursively enumerable, computably enumerable, semidecidable or provable if: There is an algorithm that, when given an input number, eventually halts if and only if the input is an element of S. Or, equivalently, There is...


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 nontrival factor. Although much more efficient methods of primality testing are known, the existence of any effective method is enough to establish decidability. A primality test is an algorithm for determining whether an input number is prime. ...


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. In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ... In computability theory, an undecidable problem is a problem whose language is not a recursively enumerable set. ... Complexity theory is part of the theory of computation dealing with the resources required during computation to solve a given problem. ... In mathematics and related technical fields, a mathematical object is complete if nothing needs to be added to it. ... To meet Wikipedias quality standards, this article or section may require cleanup. ... In computational complexity theory, SL (Symmetric Logspace) is the complexity class of problems log-space reducible to USTCON, which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the same...


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. The Entscheidungsproblem (German for decision problem) is the challenge in symbolic logic to find a general algorithm which decides for given first-order statements whether they are universally valid or not. ... David Hilbert (January 23, 1862, Wehlau, East Prussia – February 14, 1943, Göttingen, Germany) was a German mathematician, recognized as one of the most influential mathematicians of the 19th and early 20th centuries. ... The ignorabimus, short for the Latin tag ignoramus et ignorabimus meaning we do not know and will not know, stood for a pessimistic (in one sense) position on the limits on scientific knowledge, in the thought of the nineteenth century. ... David Hilbert (January 23, 1862, Wehlau, East Prussia – February 14, 1943, Göttingen, Germany) was a German mathematician, recognized as one of the most influential mathematicians of the 19th and early 20th centuries. ... In computability theory the halting problem is a decision problem which can be informally stated as follows: Given a description of a program and a finite input, decide whether the program finishes running or will run forever, given that input. ...


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. 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. Notable examples include the traveling salesman problem which asks for the route taken by the salesman, and the integer factorization 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. In the mathematical subfield of set theory, the indicator function, or characteristic function, is a function defined on a set X which is used to indicate membership of an element in a subset A of X. Remark. ...


References

  • 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

  Results from FactBites:
 
Decision problem - Wikipedia, the free encyclopedia (702 words)
In complexity theory, we attempt to categorize decision problems based on how "difficult" they are, in terms of the computational resources needed by the most efficient algorithms for that decision problem.
In this sense, a decision problem is equivalent to a formal language.
Nearly every problem can be cast as a decision problem by using reductions, often with little effect on the amount of time or space needed to solve the problem.
Knapsack problem - Wikipedia, the free encyclopedia (804 words)
Both the general knapsack problem and the subset sum problem are NP-hard, and this has led to attempts to use subset sum as the basis for public key cryptography systems, such as Merkle-Hellman.
This does not contradict the fact that the knapsack problem is NP-complete, since C, unlike n, is not polynomial in the length of the input to the problem.
The length of the input to the problem is proportional to the number of bits in C, not to C itself.
  More results at FactBites »

 
 

COMMENTARY     


Share your thoughts, questions and commentary here
Your name
Your comments

Want to know more?
Search encyclopedia, statistics and forums:

 


Press Releases |  Feeds | Contact
The Wikipedia article included on this page is licensed under the GFDL.
Images may be subject to relevant owners' copyright.
All other elements are (c) copyright NationMaster.com 2003-5. All Rights Reserved.
Usage implies agreement with terms, 1022, m