A promise problem is a pair of disjoint sets of inputs 
specifying yes and no instances. An algorithm must
accept every input in 
and reject every input in 
, but its behavior on inputs outside 
is unrestricted. The promise is that the input belongs
to this union.
An ordinary decision problem is the special case in which 
contains every possible input. Promise problems naturally express approximation tasks
where an input is guaranteed to lie on one side of a gap.
For example, QMA consists of promise problems for which a quantum algorithm running in polynomial
time checks a supplied quantum certificate. The certificate is a state of a number
of qubits bounded by a polynomial
in the input length. For each yes instance, some certificate must be accepted with
probability at least 
. For each no instance, every certificate must be accepted
with probability at most 
. No correctness requirement applies to inputs outside the
promise.
