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.
There are no requirements on the output if the input does not belong to the promise.
, then this is also a decision problem, and the promise is said to be trivial.
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 particular, it is very easy to check if a given graph is cyclic.
However, the promised property could be difficult to evaluate.
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.