# Difference between revisions of "Complexity Zoo:List of Hierarchies"

Jump to navigation
Jump to search

m (1 revision: Complexity zoo import.) |
(Add QCPH, QPH) |
||

Line 11: | Line 11: | ||

* [[Complexity Zoo:P#ph|PH]] - Polynomial-Time Hierarchy | * [[Complexity Zoo:P#ph|PH]] - Polynomial-Time Hierarchy | ||

* [[Complexity Zoo:P#phcc|PH<sup>cc</sup>]] - Polynomial Communication Complexity Hierarchy | * [[Complexity Zoo:P#phcc|PH<sup>cc</sup>]] - Polynomial Communication Complexity Hierarchy | ||

+ | * [[Complexity Zoo:Q#qcph|QCPH]] - Quantum Classical Polynomial-Time Hierarchy | ||

+ | * [[Complexity Zoo:Q#qph|QPH]] - Quantum Polynomial-Time Hierarchy |

## Latest revision as of 02:45, 7 December 2018

*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

The concept of a **hierarchy** of complexity classes is common enough that we list here some of the more notable examples of classes that are defined as the unions of hierarchies.

- AH - Arithmetic Hierarchy
- BH - Boolean Hierarchy
- CH - Counting Hierarchy
- EH - Exponential-Time, Linear-Exponent Hierarchy
- FH - Fourier Hierarchy
- PH - Polynomial-Time Hierarchy
- PH
^{cc}- Polynomial Communication Complexity Hierarchy - QCPH - Quantum Classical Polynomial-Time Hierarchy
- QPH - Quantum Polynomial-Time Hierarchy