Template:複雑性クラス

表話編歴主な複雑性クラス(一覧)
実用的な時間で解けるクラス	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P完全 ZPP RP BPP BQP APX
実用的な時間で解けないと疑われているクラス	UP NP NP完全 NP困難 co-NP co-NP完全 AM QMA PH ⊕P PP #P #P完全 IP PSPACE
実用的な時間では解けないクラス	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL
クラス階層	多項式階層指数階層グジェゴルチク階層算術的階層ブーリアン階層
クラスの族	DTIME NTIME DSPACE NSPACE PCP 対話型証明系