Promise Problem - Revision history

Srikar at 08:55, 1 July 2020

2020-07-01T08:55:13Z

Srikar at 08:53, 1 July 2020

2020-07-01T08:53:48Z

Srikar: 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..."

2020-07-01T08:53:17Z

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..."

New page

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.

← Older revision		Revision as of 08:55, 1 July 2020
Line 5:		Line 5:
	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.
		+
		+	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.

@@ Line 2: / Line 2: @@
 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.