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 seen as 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. The promise is that the input does indeed belong to $L_{\text{YES}}\cup L_{\text{NO}}$. There are no requirements on the output if the input does not belong to $L_{\text{YES}}\cup L_{\text{NO}}$. If $L_{\text{YES}}\cup L_{\text{NO}}=\{0,1\}^{*}$, then this is a decision problem.

See also

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