Σ¹₁复杂度类可判定性及多项式层次归属相关技术问询

首先得戳破你的核心误解：你把算术层次（Arithmetical Hierarchy）里的Σ¹₁和多项式层次（Polynomial Hierarchy）里的Σ₁^P（也就是我们常说的NP）搞混了——这俩符号长得像，但完全是两个不同理论体系里的复杂度类，差了十万八千里。

咱们一步步拆解：

• 两个层次的本质区别：
  多项式层次是计算复杂性理论的范畴，研究的是可判定问题中，能用多项式时间/空间资源解决或验证的问题，比如P、NP、PSPACE都属于这个体系里的可判定类。而算术层次是递归论（不可计算性理论）的范畴，研究的是不可判定问题的分层，Σ¹₁是这个层次里的第一层，对应的是二阶逻辑公式的可满足性这类问题，本身就属于不可判定的范围，和多项式层次没有包含关系。

• Σ¹₁-hard意味着什么：
  当论文说一个问题是Σ¹₁-hard时，意思是这个问题的难度至少和Σ¹₁类中最难的问题相当。而Σ¹₁类本身就包含大量不可判定的问题——甚至比经典的停机问题（属于算术层次的Σ₁^0）还要难，这就是“高度不可判定”的含义：它不是普通的不可判定，而是属于更高阶的不可判定层次，连递归可枚举的边界都突破了。

• 你的PSPACE误区：
  Σ¹₁根本不在PSPACE里！你肯定是把Σ₁^P（NP，多项式层次的第一层，属于PSPACE的子集）和Σ¹₁搞混了。PSPACE是可判定的，而Σ¹₁是完全超出可判定范围的，两者没有任何包含关系。

总结一下：你之前的错误源于把符号相似的两个不同复杂度类搞混了，算术层次的Σ¹₁和多项式层次完全不搭边，Σ¹₁-hard确实是高度不可判定的，和PSPACE没有交集。

内容的提问来源于stack exchange，提问作者Ayrat