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.