Complexity Zoo:List of Hierarchies

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
• PH^cc - Polynomial Communication Complexity Hierarchy
• QCPH - Quantum Classical Polynomial-Time Hierarchy
• QEPH - Entangled Quantum Polynomial-Time Hierarchy
• QPH - Quantum Polynomial-Time Hierarchy