多項式階層
Σ k P {\displaystyle \Sigma _{k}^{\rm {P}}} の完全問題として k回の量化子交替のある「限量記号付きブール式問題」(QBFk または QSATk と略記される)がある。これは充足可能性問題を Σ k P {\displaystyle \Sigma _{k}^{\rm {P}}} 向けにしたものである。この問題では、与えられるブール論理式 f の変数は k 個の集合 X1, ..., Xk に分けられる。ここで次が真かどうかを決定しなくてはならない。 ∃ X 1 ∀ X 2 ∃ X 3 ... f {\displaystyle \exists X_{1}\forall X_{2}\exists X_{3}\ldots f} すなわち、X1 に f を満足する値の組合せがあり、かつ X2 の値の全ての組合せが f を満足し、かつ X3 に f を満足する値の組合せがあり、... という組合せが存在するかどうか、という問題である。この順序の問題は Σ k P {\displaystyle \Sigma _{k}^{\rm {P}}} について完全である。全称記号が最初にあって、次が存在記号という順序になっている問題は Π k P {\displaystyle \Pi _{k}^{\rm {P}}} について完全である。