10
$\begingroup$

From Wikipedia:

The type of computational problem: The most commonly used problems are decision problems. However, complexity classes can be defined based on function problems, counting problems, optimization problems, promise problems, etc.

I also saw the definitions of NP-complete, NP-hard, NP, ..., are defined for decision problems only. I wonder why that is the case?

Is it because any other problem can be equivalently converted to a decision problem?

$\endgroup$
9
$\begingroup$

Oftentimes decision problems are used because they allow a precise and simple definition of the problem and, as stated, many other problems can be converted to an equivalent decision problem.

Other types of problems are also considered in complexity theory, for instance Function Problems and Search Problems.

$\endgroup$
  • $\begingroup$ Thanks! (1) How are the conversions done? (2) Also are the conversions required to be computable and within some time complexity? $\endgroup$ – Tim Oct 4 '12 at 22:14
  • 4
    $\begingroup$ @Tim: perhaps my answer to a similar question can add further details: complexity-of-decision-problems-vs-computing-functions $\endgroup$ – Vor Oct 5 '12 at 8:07
  • 1
    $\begingroup$ Also this and this one. (cc @Vor) $\endgroup$ – Raphael Oct 5 '12 at 10:59
5
$\begingroup$

there are probably many different ways to answer this question however one key element is historical precedent. the disproof of the existence of an algorithm for the halting problem in 1936 by Turing uses the halting problem as a decision problem. this was in turn based on (and resolved negatively) Hilberts Entscheidungsproblem (1928) that asked for a systematic method of determining the truth or falsity of any well formed mathematical statement ie also a decision problem.

this in turn has some similarity to Hilberts 10th problem dating to 1900 that asks for the solution of integer Diophantine equations (many of his 23 frontier/pivotal research problems were stated as decision problems). yet note the Entscheidungsproblem even rooted in a much earlier concept of Leibniz as wikipedia states:

The origin of the Entscheidungsproblem goes back to Gottfried Leibniz, who in the seventeenth century, after having constructed a successful mechanical calculating machine, dreamt of building a machine that could manipulate symbols in order to determine the truth values of mathematical statements.

also note that Diophantine equations date to the Greeks who were some of the 1st to consider, study, and emphasize the importance of mathematical proof. there are at least two important problems from number theory, still unresolved with much modern research, due to the Greeks: existence of infinite twin primes, and existence of odd perfect numbers.

note some "decision problems" (ie in the form of searching for proofs to open math conjectures) literally took hundreds of years to resolve eg Fermats Last Theorem, over 3.5 centuries, also in number theory.

so decision problems are very old, but even while simply stated can be extremely hard, and are essentially rooted in the question "is this statement true or false" relative to existence of proof(s). at the heart its a core mathematical concept. moreover it keeps reappearing in modern places in a fundamental and reminiscent way such as the P vs NP question (~1971) where the NP class can be defined/framed in terms of halting of an NP machine and solution of the satisfiability problem in P time.

$\endgroup$
  • $\begingroup$ non-decision problems are also extremely old. Given a number: factor it, is much older than Fermat's Last Theorem and still not completely satisfactorily resolved. $\endgroup$ – Peter Shor Oct 8 '12 at 16:25
  • $\begingroup$ @peter which question is older? (a) factor number x [function problem] (b) is number x prime? [decision problem] $\endgroup$ – vzn Oct 8 '12 at 18:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.