A promise problem is a generalization of a decision problem. It is defined by two decision problems and with . A Turing machine decides a promise problem if, for any , it accepts when and rejects if . Behavior is undefined when (this is the promise: that is in one of the two sets).
If then this is just the decision problem for .
|Date of creation||2013-03-22 13:02:27|
|Last modified on||2013-03-22 13:02:27|
|Last modified by||Henry (455)|