Difference between revisions of "Promise Problem"
Jump to navigation
Jump to search
(Created page with "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 r...") |
|||
| Line 2: | Line 2: | ||
problem Π consists of two disjoint sets of strings (ΠY, ΠN), corresponding to yes | 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 | and no instances respectively. All of the complexity classes that we consider—for | ||
| − | |||
| − | |||
| − | |||
instance, SZKP, CZKP, SZKA, and CZKA—generalize to promise problems | instance, SZKP, CZKP, SZKA, and CZKA—generalize to promise problems | ||
in a natural way; completeness and zero knowledge are required for yes instances, | in a natural way; completeness and zero knowledge are required for yes instances, | ||
and soundness is required for no instances. | and soundness is required for no instances. | ||
Revision as of 08:53, 1 July 2020
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.
