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:
“Martin Pawley: Do ya think maybe’s there’s a chance we still might find her?
Ethan Edwards: Injun’ll chase a thing ‘til he thinks he’s chased it enough. Then he quits. Same way when he runs. Seems like he never learns there’s such a thing as a critter that’ll just keep comin’ on. So we’ll find ‘em in the end. I promise ya. We’ll find ‘em, just as sure as the turnin’ of the earth.”
—Frank S. Nugent (1908–1965)
“What had really caused the women’s movement was the additional years of human life. At the turn of the century women’s life expectancy was forty-six; now it was nearly eighty. Our groping sense that we couldn’t live all those years in terms of motherhood alone was “the problem that had no name.” Realizing that it was not some freakish personal fault but our common problem as women had enabled us to take the first steps to change our lives.”
—Betty Friedan (20th century)