Promise Problem

A decision problem with some inputs excluded. More precisely, a promise problem Π consists of two disjoint sets of strings (ΠY, ΠN), corresponding to yes and no instances respectively. All of the complexity classes that we consider—for instance, SZKP, CZKP, SZKA, and CZKA—generalize to promise problems in a natural way; completeness and zero knowledge are required for yes instances, and soundness is required for no instances.

Roughly speaking, a promise problem [ESY] is a decision problem where some inputs are excluded. Formally, a promise problem is specified by two disjoint sets of strings Π = (ΠY, ΠN), where we call ΠY the set of yes instances and ΠN the set of no instances. Such a promise problem is associated with the following computational problem: given an input that is “promised” to lie in ΠY ∪ ΠN, decide whether it is in ΠY or in ΠN. Note that languages are a special case of promise problems (namely, a language L over alphabet Σ corresponds to the promise problem (L, Σ∗ \ L)). Thus working with promise problems makes our results more general. Moreover, even to prove our results just for languages, it turns out to be extremely useful to work with promise problems along the way. We refer the reader to the recent survey of Goldreich [Gol2] for more on the utility and subtleties of promise problems.