Complexity Zoo:Z

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

---

ZAM^cc - ZBQP - ZK - ZPE - ZP•L - ZPP - ZPP^cc - ZPTIME(f(n)) - ZQP

ZAM^cc: Zero-Information Arthur-Merlin Communication Complexity

Similar to AM^cc 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 coNP^cc [GPW16a].

Unlike with other communication complexity classes, it is not known whether every function can be computed with O(n) communication in the ZAM^cc 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ⁿ) 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, ZBQP^ZBQP = 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 2^O(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 RP ∩ coRP.

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

---

ZPP^cc: Communication Complexity ZPP

Equals P^cc if defined in terms of total functions; is not contained in ⊕P^cc 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 ZQP^ZQP is larger than ZQP [BW03]; c.f. with ZBQP.