Difference between revisions of "Complexity Zoo:Z"
m (1 revision: Complexity zoo import.)
Revision as of 03:10, 18 November 2012
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 perefect 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.)
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.