이론은 얼마나 복잡합니까? $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$ 1 차 문장으로 $\hat{\varphi}$ 그런 ${\bf 2}\models\hat{\varphi}$ iff $\varphi$만족 스럽습니다. 물론 이중적으로 이것은$\mathsf{coSAT}$ 감소 $\Pi_1$ 파편.

수량자를 추가하는 동작을 고려할 때 대답에 대한 자연스러운 추측은 다항식 계층 구조에서 수준의 합집합이어야한다는 것입니다.하지만 세부 사항을 즉시 볼 수는 없습니다.

Answer 1

Quantified Boolean Formulas는 PSPACE 완전하고 순수 1 차 이론으로 축소 될 수 있습니다. $2$, PSPACE 하드입니다. 반면에 PSPACE에도 분명히 있습니다 (명백한 재귀 알고리즘은 공간 사용에서 다항식이기 때문입니다). 그래서 그것은 PSPACE-complete입니다.