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 particular subset of all possible inputs.^[1] Unlike decision problems, the yes instances (the inputs for which an algorithm must return yes) and no instances do not exhaust the set of all inputs. Intuitively, the algorithm has been promised that the input does indeed belong to set of yes instances or no instances. There may be inputs which are neither yes nor no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything, and may even not halt.

Formal definition

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

Examples

Many natural problems are actually promise problems. For instance, consider the following problem: Given a

to evaluate, yet the promise problem is easy to solve since checking for cycles of size 4 can be done in polynomial time.

See also

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

References

Surveys

• Goldreich, Oded (2006). "On Promise Problems (a survey)". Theoretical Computer Science: Essays in memory of Shimon Even.
  doi:10.1007/11685654_12
  .
• Sahai, A.; Vadhan, S.P. (1997). "A complete promise problem for statistical zero-knowledge". FOCS 1997. pp. 448–457.
  doi:10.1109/SFCS.1997.646133
  .
• Even, Shimon;
  doi:10.1016/S0019-9958(84)80056-X
  .