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. 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 or no. If such an input is given to an algorithm for solving a promise problem, the algorithm is allowed to output anything.
Read more about Promise Problem: Formal Definition, Examples
Famous quotes containing the words promise and/or problem:
“The first promise exchanged by two beings of flesh was at the foot of a rock that was crumbling into dust; they took as witness for their constancy a sky that is not the same for a single instant; everything changed in them and around them, and they believed their hearts free of vicissitudes. O children! always children!”
—Denis Diderot (1713–1784)
“The problem with marriage is that it ends every night after making love, and it must be rebuilt every morning before breakfast.”
—Gabriel García Márquez (b. 1928)