Loading article…
これは、計算複雑性理論における複雑性クラスの一覧です。その他の計算および複雑性に関するトピックについては、「計算可能性と複雑性に関するトピック一覧」を参照してください。
これらのクラスの多くには、元のクラスに含まれるすべての言語の補語からなる「共」パートナーが存在します。例えば、言語LがNPに属する場合、Lの補語はco-NPに属します。（これはNPの補語がco-NPであることを意味するものではありません。両方のクラスに属することが知られている言語もあれば、どちらにも属さないことが知られている言語もあります。）
あるクラスにおける「最も難しい問題」とは、そのクラスに属する他のすべての問題がその問題に還元できるような問題を指します。