HOME

TheInfoList



OR:

In
computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ...
and
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, a decision problem is a computational problem that can be posed as a
yes–no question In linguistics, a yes–no question, also known as a binary question, a polar question, or a general question is a question whose expected answer is one of two choices, one that provides an affirmative answer to the question versus one that provi ...
of the input values. An example of a decision problem is deciding by means of an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
whether a given natural number is
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only way ...
. Another is the problem "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?". The answer is either 'yes' or 'no' depending upon the values of ''x'' and ''y''. A method for solving a decision problem, given in the form of an
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
, is called a decision procedure for that problem. A decision procedure for the decision problem "given two numbers ''x'' and ''y'', does ''x'' evenly divide ''y''?" would give the steps for determining whether ''x'' evenly divides ''y''. One such algorithm is long division. If the remainder is zero the answer is 'yes', otherwise it is 'no'. A decision problem which can be solved by an algorithm is called ''decidable''. Decision problems typically appear in mathematical questions of decidability, that is, the question of the existence of an
effective method In logic, mathematics and computer science, especially metalogic and computability theory, an effective method Hunter, Geoffrey, ''Metalogic: An Introduction to the Metatheory of Standard First-Order Logic'', University of California Press, 1971 ...
to determine the existence of some object or its membership in a set; some of the most important problems in mathematics are undecidable. 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 Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has sinc ...
, meanwhile, categorizes ''undecidable'' decision problems by Turing degree, which is a measure of the noncomputability inherent in any solution.


Definition

A ''decision problem'' is a yes-or-no question on an
infinite set In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable. Properties The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only ...
of inputs. It is traditional to define the decision problem as the set of possible inputs together with the set of inputs for which the answer is ''yes''. These inputs can be natural numbers, but can also be values of some other kind, like binary
string String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects Arts, entertainment, and media Films * ''Strings'' (1991 film), a Canadian anim ...
s or strings over some other
alphabet An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a s ...
. The subset of strings for which the problem returns "yes" is a
formal language In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules. The alphabet of a formal language consists of s ...
, and often decision problems are defined as formal languages. Using an encoding such as
Gödel numbering In mathematical logic, a 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 developed by Kurt Gödel for the proof of ...
, any string can be encoded as a natural number, via which a decision problem can be defined as a subset of the natural numbers. Therefore, the algorithm of a decision problem is to compute the
characteristic function In mathematics, the term "characteristic function" can refer to any of several distinct concepts: * The indicator function of a subset, that is the function ::\mathbf_A\colon X \to \, :which for a given subset ''A'' of ''X'', has value 1 at point ...
of a subset of the natural numbers.


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 A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating wheth ...
are known, the existence of any effective method is enough to establish decidability.


Decidability

A decision problem is ''decidable'' or ''effectively solvable'' if the set of inputs (or natural numbers) for which the answer is yes is a
recursive set In computability theory, a set of natural numbers is called computable, recursive, or decidable if there is an algorithm which takes a number as input, terminates after a finite amount of time (possibly depending on the given number) and correctly ...
. A problem is ''partially decidable'', ''semidecidable'', ''solvable'', or ''provable'' if the set of inputs (or natural numbers) for which the answer is yes is a
recursively enumerable set In computability theory, a set ''S'' of natural numbers is called computably enumerable (c.e.), recursively enumerable (r.e.), semidecidable, partially decidable, listable, provable or Turing-recognizable if: *There is an algorithm such that the ...
. Problems that are not decidable are ''undecidable''. For those it is not possible to create an algorithm, efficient or otherwise, that solves them. The
halting problem In computability theory, the halting problem is the problem of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever. Alan Turing proved in 1936 that a ...
is an important undecidable decision problem; for more examples, see list of undecidable problems.


Complete problems

Decision problems can be ordered according to many-one reducibility and related to feasible reductions such as polynomial-time reductions. A decision problem ''P'' is said to be '' complete'' for a set of decision problems ''S'' if ''P'' is a member of ''S'' and every problem in ''S'' can be reduced to ''P''. Complete decision problems are used in
computational complexity theory In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
to characterize
complexity class In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory. In general, a complexity class is defined in terms ...
es of decision problems. For example, the
Boolean satisfiability problem In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies ...
is complete for the class NP of decision problems under polynomial-time reducibility.


Function problems

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''?". A function problem consists of a
partial function In mathematics, a partial function from a set to a set is a function from a subset of (possibly itself) to . The subset , that is, the domain of viewed as a function, is called the domain of definition of . If equals , that is, if is ...
''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 computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
(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 In mathematics, the term "characteristic function" can refer to any of several distinct concepts: * The indicator function of a subset, that is the function ::\mathbf_A\colon X \to \, :which for a given subset ''A'' of ''X'', has value 1 at point ...
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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
problem and its co-NP-complete
complement A complement is something that completes something else. Complement may refer specifically to: The arts * Complement (music), an interval that, when added to another, spans an octave ** Aggregate complementation, the separation of pitch-clas ...
is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.


Optimization problems

Unlike decision problems, for which there is only one correct answer for each input, optimization problems are concerned with finding the ''best'' answer to a particular input. Optimization problems arise naturally in many applications, such as the
traveling salesman problem The travelling salesman problem (also called the travelling salesperson problem or TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each cit ...
and many questions in
linear programming Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is ...
. There are standard techniques for transforming function and optimization problems into decision problems. For example, in the traveling salesman problem, the optimization problem is to produce a tour with minimal weight. The associated decision problem is: for each ''N'', to decide whether the graph has any tour with weight less than ''N''. By repeatedly answering the decision problem, it is possible to find the minimal weight of a tour. Because the theory of decision problems is very well developed, research in complexity theory has typically focused on decision problems. Optimization problems themselves are still of interest in computability theory, as well as in fields such as
operations research Operations research ( en-GB, operational research) (U.S. Air Force Specialty Code: Operations Analysis), often shortened to the initialism OR, is a discipline that deals with the development and application of analytical methods to improve dec ...
.


See also

*
ALL (complexity) In computability and complexity theory, ALL is the class of all decision problems. Relations to other classes ALL contains all of the complex classes of decision problems, including RE and co-RE. External links * Complexity classes ...
*
Computational problem In theoretical computer science, a computational problem is a problem that may be solved by an algorithm. For example, the problem of factoring :"Given a positive integer ''n'', find a nontrivial prime factor of ''n''." is a computational probl ...
*
Decidability (logic) In logic, a true/false decision problem is decidable if there exists an effective method for deriving the correct answer. Zeroth-order logic (propositional logic) is decidable, whereas first-order and higher-order logic are not. Logical systems ...
– for the problem of deciding whether a formula is a consequence of a logical theory. *
Search problem In computational complexity theory and computability theory, a search problem is a type of computational problem represented by a binary relation. If ''R'' is a binary relation such that field(''R'') ⊆ Γ+ and ''T'' is a Turing machine, then '' ...
* Counting problem (complexity) * Word problem (mathematics)


References

* * * * * * {{Authority control Computational problems Computability theory