# promise problem

A promise problem is a generalization of a decision problem. It is defined by two decision problems $L_{1}$ and $L_{2}$ with $L_{1}\cap L_{2}=\emptyset$. A Turing machine decides a promise problem if, for any $x\in L_{1}\cup L_{2}$, it accepts when $x\in L_{1}$ and rejects if $x\in L_{2}$. Behavior is undefined when $x\notin L_{1}\cup L_{2}$ (this is the promise: that $x$ is in one of the two sets).

If $L_{2}=\Gamma^{+}\setminus L_{1}$ then this is just the decision problem for $L_{1}$.

Title promise problem PromiseProblem 2013-03-22 13:02:27 2013-03-22 13:02:27 Henry (455) Henry (455) 4 Henry (455) Definition msc 68Q25