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:
“The conviction that the best way to prepare children for a harsh, rapidly changing world is to introduce formal instruction at an early age is wrong. There is simply no evidence to support it, and considerable evidence against it. Starting children early academically has not worked in the past and is not working now.”
—David Elkind (20th century)
“The very definition of the real becomes: that of which it is possible to give an equivalent reproduction.... The real is not only what can be reproduced, but that which is always already reproduced. The hyperreal.”
—Jean Baudrillard (b. 1929)