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 parent who loves his child dearly but asks for nothing in return might qualify as a saint, but he will not qualify as a parent. For a child who can claim love without meeting any of the obligations of love will be a self-centered child and many such children have grown up in our time to become petulant lovers and sullen marriage partners because the promise of unconditional love has not been fulfilled.”
—Selma H. Fraiberg (20th century)
“Every reform was once a private opinion, and when it shall be a private opinion again, it will solve the problem of the age.”
—Ralph Waldo Emerson (1803–1882)