Promise problem

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 when x ∈ L₁ and rejects if x ∈ L₂. Behavior is undefined when x ∉ L₁ ∪ L₂ (this is the promise: that x is in one of the two sets).

If L₂ = Γ⁺ \ L₁ then this is just the decision problem for L₁.

promise problem at PlanetMath.