Promise problem

Promise problem

In computability theory, a promise problem is a generalization of a decision problem. It is defined by two decision problems "L"1 and "L"2 with "L"1 ∩ "L"2 = ∅. A Turing machine decides a promise problem if, for any "x" ∈ "L"1 ∪ "L"2, it accepts "x" if "x" ∈ "L"1 and rejects "x" if "x" ∈ "L"2. There are no requirements on the behavior of the Turing machine when "x" ∉ "L"1 ∪ "L"2 (this is the promise: that "x" is in one of the two sets).

If "L"2 is equal to Γ+ "L"1, the set of all words not in "L1, then this is just the decision problem for "L"1.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно сделать НИР?

Look at other dictionaries:

  • promise — Giving one s word that one will do something creates a reason for action in the future. But when the time comes, by keeping the promise one seems to act because one has done something in the past, rather than for the sake of promoting some goal… …   Philosophy dictionary

  • promise — 01. After he got arrested for drunk driving, he [promised] to stop drinking, but two weeks later he was at the bar again. 02. The little boy [promised] his mother that he would come straight home after school. 03. Henry s teachers were confident… …   Grammatical examples in English

  • Computational problem — In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring Given a positive integer n, find a nontrivial prime …   Wikipedia

  • John F. Kennedy: The American Promise to African Americans — ▪ Primary Source              On June 11, 1963, a momentous event occurred at the University of Alabama. Two African American residents of Alabama, who were clearly qualified for studies at the state s highest institution of learning, had been… …   Universalium

  • Lattice problem — In computer science, lattice problems are a class of optimization problems on lattices. The conjectured intractability of such problems is central to construction of secure lattice based cryptosystems. For applications in such cryptosystems,… …   Wikipedia

  • Is–ought problem — David Hume raised the is ought problem in his Treatise of Human Nature The is–ought problem in meta ethics as articulated by Scottish philosopher and historian, David Hume (1711–1776), is that many writers make claims about what ought to be on… …   Wikipedia

  • Is-ought problem — In meta ethics, the is ought problem was raised by David Hume (Scottish philosopher and historian, 1711 ndash;1776), who noted that many writers make claims about what ought to be on the basis of statements about what is . However, there seems to …   Wikipedia

  • Aquaculture: Fulfilling Its Promise — ▪ 1999 Introduction by Anne Platt McGinn       For 25 centuries fish farming (aquaculture) has been a mainstay of Asian agriculture. Throughout China, India, and Thailand, it prospered on traditional small scale farms. In recent years, however,… …   Universalium

  • PCP theorem — In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and… …   Wikipedia

  • Valiant-Vazirani theorem — The Valiant Vazirani Theorem was proven by Leslie Valiant and Vijay Vazirani in their paper titled NP is as easy as detecting unique solutions published in 1986. The theorem states that if there is a polynomial time algorithm for UNIQUE SAT, then …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”