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
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