抄録

○小林弘二（所属なし）

本論文では複雑性クラスのNCとPHの階層が正当であることを示す．NCとPHの階層の正当性を証明するために，複雑性クラスの崩壊とその影響を考える．
NCのいずれかの階層が崩壊していると仮定すると，決定問題を構成する任意の基底問題をその階層に埋め込むことができる．つまりその階層は任意の決定問題を構成することができる．しかし，決定問題にはEXPSPACEを計算可能な決定問題も含まれるため，階層定理と矛盾する．よってNCの階層は崩壊しておらず，正当である．
同様にしてPHの正当性を示すことができる．