Complexity Zoo:List of Hierarchies

From Complexity Zoo
Revision as of 22:10, 17 November 2012 by Admin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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
  • PHcc - Polynomial Communication Complexity Hierarchy
Personal tools

Variants
Actions
Navigation
Toolbox