の理論はどれほど複雑ですか $2$？

Question

動機 https://math.stackexchange.com/questions/3757967/are-there-any-sets-of-axioms-that-have-an-efficient-algorithm-for-all-provable-s、私は尋ねたいです：

2要素の純粋な集合の1次理論の複雑さは何ですか $\bf 2$？

（置き換えても答えは同じになることに注意してください ${\bf 2}$ 複数の要素を持つ任意の有限の純粋なセットによって。）

リンクされた質問に対する私の答えの議論は、両方が $\mathsf{SAT}$ に減少します $\Sigma_1$ この問題の断片：命題文を変換する効率的な方法があります $\varphi$ 一次文に $\hat{\varphi}$ そのような ${\bf 2}\models\hat{\varphi}$ iff $\varphi$充足可能です。もちろん、これは二重に意味します$\mathsf{coSAT}$ に減少します $\Pi_1$ 断片。

数量詞を追加する動作を考慮すると、答えの自然な推測は、それが多項式階層のレベルの和集合である必要があるということですが、詳細はすぐにはわかりません。

Answer 1

Quantified Boolean FormulasがPSPACE完全であり、の純粋な1次理論に還元できることを考えると $2$、それはPSPACEです-難しいです。一方、それは明らかにPSPACEにもあります（明らかな再帰的アルゴリズムはスペース使用量の多項式であるため）。つまり、PSPACEコンプリートです。