Formal Definition
A decision problem can be associated with a language, where the problem is to accept all inputs in and reject all inputs not in . For a promise problem, there are two languages, and, which must be disjoint, which means, such that all the inputs in are to be accepted and all inputs in are to be rejected. The set is called the promise. There are no requirements on the output if the input does not belong to the promise. If the promise equals, then this is also a decision problem, and the promise is said to be trivial.
Read more about this topic: Promise Problem
Famous quotes containing the words formal and/or definition:
“True variety is in that plenitude of real and unexpected elements, in the branch charged with blue flowers thrusting itself, against all expectations, from the springtime hedge which seems already too full, while the purely formal imitation of variety ... is but void and uniformity, that is, that which is most opposed to variety....”
—Marcel Proust (1871–1922)
“Was man made stupid to see his own stupidity?
Is God by definition indifferent, beyond us all?
Is the eternal truth man’s fighting soul
Wherein the Beast ravens in its own avidity?”
—Richard Eberhart (b. 1904)