Difference between revisions of "Complexity Zoo:Z"

From Complexity Zoo
Jump to navigation Jump to search
 
(6 intermediate revisions by 2 users not shown)
Line 2: Line 2:
 
{{CZ-Letter-Menu|Z}}
 
{{CZ-Letter-Menu|Z}}
  
 +
 +
===== <span id="zamcc" style="color:red">ZAM<sup>cc</sup></span>: Zero-Information Arthur-Merlin Communication Complexity =====
 +
 +
Similar to [[Complexity Zoo:A#amcc|AM<sup>cc</sup>]] except that on each yes-input, the distribution of Merlin’s proof must leak no information about the input and moreover, this proof must be unique for each outcome of Arthur’s (i.e., Alice's and Bob's) randomness.
 +
 +
Contained in [[Complexity Zoo:C#conpcc|coNP<sup>cc</sup>]] [[zooref#gpw16a|[GPW16a]]].
 +
 +
Unlike with other communication complexity classes, it is not known whether every function can be computed with O(n) communication in the ZAM<sup>cc</sup> model. In fact it is not even obvious that every function can be computed at all in this model, but this turns out to be the case; indeed, there is an O(2<sup>n</sup>) upper bound for every function [[zooref#gpw16a|[GPW16a]]].
 +
 +
Closely related to "private simultaneous messages" protocols in cryptography [[zooref#ar16|[AR16]]].
 +
 +
----
  
 
===== <span id="zbqp" style="color:red">ZBQP</span>: Strict Quantum [[#zpp|ZPP]] =====
 
===== <span id="zbqp" style="color:red">ZBQP</span>: Strict Quantum [[#zpp|ZPP]] =====
Line 15: Line 27:
  
 
===== <span id="zk" style="color:red">ZK</span>: Zero-Knowledge (see [[Complexity Zoo:C#czk|CZK]]) =====
 
===== <span id="zk" style="color:red">ZK</span>: Zero-Knowledge (see [[Complexity Zoo:C#czk|CZK]]) =====
Often used as a shorthand for [[C#czk|(computational zero-knowledge) CZK]], but may also be used as a general paradigm encomposing various classes ranging from perfect and statistical zero-knowledge ([[Complexity Zoo:S#szk|SZK]]) to computational ones ([[Complexity Zoo:C#czk|CZK]]), and also various forms of non-interactive zero-knowledge proof systems.
+
Often used as a shorthand for [[Complexity Zoo:C#czk|(computational zero-knowledge) CZK]], but may also be used as a general paradigm encomposing various classes ranging from perfect and statistical zero-knowledge ([[Complexity Zoo:S#szk|SZK]]) to computational ones ([[Complexity Zoo:C#czk|CZK]]), and also various forms of non-interactive zero-knowledge proof systems.
  
 
Zero-knowledge proofs were introduced in [[zooref#gmr89|[GMR89]]], and further studied in [[zooref#gmw91|[GMW91]]], which demonstrated the wide applicability of the concept.  
 
Zero-knowledge proofs were introduced in [[zooref#gmr89|[GMR89]]], and further studied in [[zooref#gmw91|[GMW91]]], which demonstrated the wide applicability of the concept.  
Line 25: Line 37:
  
 
ZPE = [[Complexity Zoo:E#ee|EE]] if and only if [[#zpp|ZPP]] = [[Complexity Zoo:E#exp|EXP]] [[zooref#ikw01|[IKW01]]].
 
ZPE = [[Complexity Zoo:E#ee|EE]] if and only if [[#zpp|ZPP]] = [[Complexity Zoo:E#exp|EXP]] [[zooref#ikw01|[IKW01]]].
 +
 +
----
 +
 +
===== <span id="zpdotl" style="color:red">ZP•L</span>: Zero-Error Probabilistic [[Complexity Zoo:L#l|L]] with Two Way Access to Randomness =====
 +
 +
Has the same relationship to [[Complexity Zoo:B#bpdotl|BP•L]] as [[#zpp|ZPP]] has to [[Complexity Zoo:B#bpp|BPP]]. More specifically, the set of languages with a log space, polynomial time Turing machine using a read only randomness tape such that on input x:
 +
 +
1. With high probability over the random bits used in the randomness tape will the machine correctly output whether x is in the language.
 +
 +
2. The machine will either wither correctly output whether x is in the language, or output 'unknown'.
 +
 +
Contains [[Complexity Zoo:B#bpl|BPL]] [[zooref#nis93|[Nis93]]].
 +
 +
Contained in [[Complexity Zoo:R#rnc|RNC]] since [[Complexity Zoo:L#l|L]] is contained in [[Complexity Zoo:N#nc|NC]] and zero sided error is weaker than one sided error.
 +
 +
Contained in [[Complexity Zoo:B#bpdotl|BP•L]].
  
 
----
 
----
Line 44: Line 72:
  
 
===== <span id="zppcc" style="color:red">ZPP<sup>cc</sup></span>: Communication Complexity [[#zpp|ZPP]] =====
 
===== <span id="zppcc" style="color:red">ZPP<sup>cc</sup></span>: Communication Complexity [[#zpp|ZPP]] =====
 +
 +
Equals [[Complexity Zoo:P#pcc|P<sup>cc</sup>]] if defined in terms of total functions; is not contained in [[Complexity Zoo:Symbols#paritypcc|&#8853;P<sup>cc</sup>]] if defined in terms of partial functions [[zooref#gpw16b|[GPW16b]]].
  
 
----
 
----

Latest revision as of 03:36, 22 October 2022

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References


Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform


ZAMcc - ZBQP - ZK - ZPE - ZP•L - ZPP - ZPPcc - ZPTIME(f(n)) - ZQP


ZAMcc: Zero-Information Arthur-Merlin Communication Complexity

Similar to AMcc except that on each yes-input, the distribution of Merlin’s proof must leak no information about the input and moreover, this proof must be unique for each outcome of Arthur’s (i.e., Alice's and Bob's) randomness.

Contained in coNPcc [GPW16a].

Unlike with other communication complexity classes, it is not known whether every function can be computed with O(n) communication in the ZAMcc model. In fact it is not even obvious that every function can be computed at all in this model, but this turns out to be the case; indeed, there is an O(2n) upper bound for every function [GPW16a].

Closely related to "private simultaneous messages" protocols in cryptography [AR16].


ZBQP: Strict Quantum ZPP

Defined as RBQP ∩ coRBQP. Equivalently, the class of problems in NP ∩ coNP such that both positive and negative witnesses are in FBQP.

For example, the language of square-free numbers is in ZBQP, because factoring is in FBQP and a factorization can be certified in ZPP (indeed in P, by [AKS02]).

Unlike EQP or ZQP, ZBQP would generalize ZPP in practice if quantum computers existed, in the sense that it provides proven answers.

Contains ZPP and is contained in RBQP and ZQP. Also, ZBQPZBQP = ZBQP. Defined here to clarify EQP and ZQP.


ZK: Zero-Knowledge (see CZK)

Often used as a shorthand for (computational zero-knowledge) CZK, but may also be used as a general paradigm encomposing various classes ranging from perfect and statistical zero-knowledge (SZK) to computational ones (CZK), and also various forms of non-interactive zero-knowledge proof systems.

Zero-knowledge proofs were introduced in [GMR89], and further studied in [GMW91], which demonstrated the wide applicability of the concept.


ZPE: Zero-Error Probabilistic E

Same as ZPP, but with 2O(n)-time instead of polynomial-time.

ZPE = EE if and only if ZPP = EXP [IKW01].


ZP•L: Zero-Error Probabilistic L with Two Way Access to Randomness

Has the same relationship to BP•L as ZPP has to BPP. More specifically, the set of languages with a log space, polynomial time Turing machine using a read only randomness tape such that on input x:

1. With high probability over the random bits used in the randomness tape will the machine correctly output whether x is in the language.

2. The machine will either wither correctly output whether x is in the language, or output 'unknown'.

Contains BPL [Nis93].

Contained in RNC since L is contained in NC and zero sided error is weaker than one sided error.

Contained in BP•L.


ZPP: Zero-Error Probabilistic Polynomial-Time

Defined as RPcoRP.

Defined as the class of problems solvable by randomized algorithms that always return the correct answer, and whose expected running time (on any input) is polynomial, in [Gil77]. (Proposition 5.5(iii) in this paper shows that the two definitions above are equivalent.)

Contains the problem of testing whether an integer is prime [SS77] [AH87].

In contrast to BPP and RP, it is not known whether showing ZPP = P requires proving superpolynomial circuit lower bounds [KI02].

There exists an oracle relative to which ZPP = EXP [Hel84a], [Hel84b], [Kur85], [Hel86].

Has the same p-measure as RP. Moreover, this measure is either zero or one. If the measure is non-zero, then ZPP = BPP = EXP [IM03].


ZPPcc: Communication Complexity ZPP

Equals Pcc if defined in terms of total functions; is not contained in ⊕Pcc if defined in terms of partial functions [GPW16b].


ZPTIME(f(n)): Zero-Error Probabilistic f(n)-Time

Same as ZPP, but with O(f(n))-time instead of polynomial-time.

For any constructible superpolynomial f, ZPTIME(f(n)) with NP oracle is not contained in P/poly [KW98].


ZQP: Zero-Error Extension Of EQP

The class of questions that can be answered by a QTM that answers yes, no, or "maybe". If the correct answer is yes, then P[no] = 0, and vice-versa; and the probability of maybe is at most 1/2. Since some of the probabilities have to vanish, ZQP has the same technical caveats as EQP.

Defined independently in [BW03] and in [Nis02].

Contains EQP and ZBQP and is contained in BQP. Equals RQP ∩ coRQP. There is an oracle such that ZQPZQP is larger than ZQP [BW03]; c.f. with ZBQP.