Promise problem

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.

Many natural problems are actually promise problems. For instance, consider the following problem: Given a directed acyclic graph, determine if the graph has a path of length 10. The yes instances are directed acyclic graphs with a path of length 10, whereas the no instances are directed acyclic graphs with no path of length 10. The promise is the set of directed acyclic graphs. In this example, the promise is easy to check. In particular, it is very easy to check if a given graph is cyclic. However, the promised property could be difficult to evaluate. For instance, consider the problem "Given a Hamiltonian graph, determine if the graph has a cycle of size 4." Now the promise is NP-hard to evaluate, yet the promise problem is easy to solve since checking for cycles of size 4 can be done in polynomial time.

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