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 3 Actually polynomial-time provers also make sense for problems in MA, which is a variant of NP where the verification of witnesses is probabilistic. All of our results easily extend to MA, but we state them for NP for simplicity. 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.