Promise problem

From Wikipedia, the free encyclopedia

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

If L₂ is equal to Γ⁺ \ L₁, the set of all words not in L₁, then this is just the decision problem for L₁.

This article incorporates material from promise problem on PlanetMath, which is licensed under the GFDL.