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.
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
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.
ZPE: Zero-Error Probabilistic E
Same as ZPP, but with 2O(n)-time instead of polynomial-time.
ZPP: Zero-Error Probabilistic Polynomial-Time
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.)
ZPPcc: Communication Complexity ZPP
ZPTIME(f(n)): Zero-Error Probabilistic f(n)-Time
Same as ZPP, but with O(f(n))-time instead of polynomial-time.
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.