多项式谱系

计算复杂度理论中，多项式谱系是一个复杂度系列。它从P、NP和反NP复杂度类逐级产生至预言机。它类似于数理逻辑中算数阶层和分析阶层，只不过是由逐级放宽资源限制而产生的。

多项式谱系有数个等价的定义。

其中P是能在多项式时间内解决的决定性问题。然后对所有${\displaystyle i\ge <!--\; \ge \; -->0}$电路${\displaystyle B}$输入${\displaystyle x}$，${\displaystyle ⟨<!--\; ⟨\; -->A,k,B,x⟩<!--\; ⟩\; -->\in <!--\; \in \; -->L}$。

是否为真。也就是说存在对${\displaystyle X_1}$的赋值，使得对所有的${\displaystyle X_2}$, 存在对${\displaystyle X_3}$的赋值，……，使得${\displaystyle f}$为真。从全称量词开始交替到存在量词再到全称量词的变体则是${\displaystyle {\mathrm{\Pi <!--\; \Pi \; -->}}_k^{\mathsf{P}}}$完备的。