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 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₁.

See also

• Computational problem
• Decision problem
• Optimization problem
• Search problem
• Counting problem (complexity)
• Function problem

promise problem at PlanetMath.