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:
“A puff of wind, a puff faint and tepid and laden with strange odours of blossoms, of aromatic wood, comes out the still night—the first sigh of the East on my face. That I can never forget. It was impalpable and enslaving, like a charm, like a whispered promise of mysterious delight.... The mysterious East faced me, perfumed like a flower, silent like death, dark like a grave.”
—Joseph Conrad (1857–1924)
“[How] the young . . . can grow from the primitive to the civilized, from emotional anarchy to the disciplined freedom of maturity without losing the joy of spontaneity and the peace of self-honesty is a problem of education that no school and no culture have ever solved.”
—Leontine Young (20th century)