利用者:Flightbridge/sandbox/Template:複雑性クラス

{@{DEFAULTSORT:Complexityclasses}} [@[Category:Mathematics navigational boxes]] [@[Category:Computer science navigational boxes]]

表話編歴重要な複雑性クラス (一覧（英語版）)
実行可能	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 PSPACE完全
実行不可能	EXPTIME NEXPTIME EXPSPACE ELEMENTARY PR R RE ALL（英語版）
クラス階層	多項式階層指数階層（英語版）グジェゴルチク階層算術的階層ブール階層（英語版）
クラスの族	DTIME NTIME DSPACE NSPACE 確率的検査可能証明対話型証明系