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:
“This is no argument against teaching manners to the young. On the contrary, it is a fine old tradition that ought to be resurrected from its current mothballs and put to work...In fact, children are much more comfortable when they know the guide rules for handling the social amenities. It’s no more fun for a child to be introduced to a strange adult and have no idea what to say or do than it is for a grownup to go to a formal dinner and have no idea what fork to use.”
—Leontine Young (20th century)
“Scientific method is the way to truth, but it affords, even in
principle, no unique definition of truth. Any so-called pragmatic
definition of truth is doomed to failure equally.”
—Willard Van Orman Quine (b. 1908)