# 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}=\mathrm{\varnothing}$. 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}={\mathrm{\Gamma}}^{+}\setminus {L}_{1}$ then this is just the decision problem for ${L}_{1}$.

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 |