Promise problem

In computational complexity theory, a promise problem is a generalization of a decision problem where the input is promised to belong to a subset of all possible inputs.

A decision problem can be associated with a language $L\in \{0,1\}^{*}$, where the problem is to accept all inputs in $L$ and reject all inputs not in $L$. For a promise problem, there are two disjoint languages, $L_{\text{YES}}$ and $L_{\text{NO}}$, with $L_{\text{YES}}\cap L_{\text{NO}}=\varnothing$, such that all inputs in $L_{\text{YES}}$ are to be accepted and all inputs in $L_{\text{NO}}$ are to be rejected. Intuitively, the algorithm has been promised that the input does indeed belong to $L_{\text{YES}}\cup L_{\text{NO}}$. This set is called the promise. There are no requirements on the output if the input does not belong to the promise. If the promise equals $\{0,1\}^{*}$, then this is also a decision problem, and the promise is said to be trivial.

See also

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

References

Surveys

• On Promise Problems (a survey in memory of Shimon Even) by Oded Goldreich.