Difference between revisions of "Complexity Zoo:List of Hierarchies"
Jump to navigation
Jump to search
(Add QCPH, QPH) |
(add DistributionPH) |
||
| (2 intermediate revisions by 2 users not shown) | |||
| Line 7: | Line 7: | ||
* [[Complexity Zoo:B#bh|BH]] - Boolean Hierarchy | * [[Complexity Zoo:B#bh|BH]] - Boolean Hierarchy | ||
* [[Complexity Zoo:C#ch|CH]] - Counting Hierarchy | * [[Complexity Zoo:C#ch|CH]] - Counting Hierarchy | ||
| + | * [[Complexity Zoo:D#distributionph|DistributionPH]] - Distribution Polynomial-Time Hierarchy | ||
* [[Complexity Zoo:E#eh|EH]] - Exponential-Time, Linear-Exponent Hierarchy | * [[Complexity Zoo:E#eh|EH]] - Exponential-Time, Linear-Exponent Hierarchy | ||
* [[Complexity Zoo:F#fh|FH]] - Fourier Hierarchy | * [[Complexity Zoo:F#fh|FH]] - Fourier Hierarchy | ||
| + | * [[Complexity Zoo:M#modph|ModPH]] - Modular Counting Hierarchy | ||
* [[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#qcph|QCPH]] - Quantum Classical Polynomial-Time Hierarchy | ||
| + | * [[Complexity Zoo:Q#qeph|QEPH]] - Entangled Quantum Polynomial-Time Hierarchy | ||
* [[Complexity Zoo:Q#qph|QPH]] - Quantum Polynomial-Time Hierarchy | * [[Complexity Zoo:Q#qph|QPH]] - Quantum Polynomial-Time Hierarchy | ||
Latest revision as of 16:14, 7 July 2024
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
- DistributionPH - Distribution Polynomial-Time Hierarchy
- EH - Exponential-Time, Linear-Exponent Hierarchy
- FH - Fourier Hierarchy
- ModPH - Modular Counting Hierarchy
- PH - Polynomial-Time Hierarchy
- PHcc - Polynomial Communication Complexity Hierarchy
- QCPH - Quantum Classical Polynomial-Time Hierarchy
- QEPH - Entangled Quantum Polynomial-Time Hierarchy
- QPH - Quantum Polynomial-Time Hierarchy