promise problem

A promise problem is a generalizationPlanetmathPlanetmath of a decision problemMathworldPlanetmath. It is defined by two decision problems L1 and L2 with L1L2=. A Turing machineMathworldPlanetmath decides a promise problem if, for any xL1L2, it accepts when xL1 and rejects if xL2. Behavior is undefined when xL1L2 (this is the promise: that x is in one of the two sets).

If L2=Γ+L1 then this is just the decision problem for L1.

Title promise problem
Canonical name PromiseProblem
Date of creation 2013-03-22 13:02:27
Last modified on 2013-03-22 13:02:27
Owner Henry (455)
Last modified by Henry (455)
Numerical id 4
Author Henry (455)
Entry type Definition
Classification msc 68Q25