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

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

---

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

---

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.