का सिद्धांत कितना जटिल है $2$?

Question

द्वारा प्रेरित https://math.stackexchange.com/questions/3757967/are-there-any-sets-of-axioms-that-have-an-efficient-algorithm-for-all-provable-s, मैं पूछना चाहता हूं:

दो-तत्व शुद्ध सेट के पहले-क्रम सिद्धांत की जटिलता क्या है $\bf 2$?

(ध्यान दें कि यदि हम प्रतिस्थापित करते हैं तो उत्तर समान होगा ${\bf 2}$ किसी भी परिमित शुद्ध सेट द्वारा एक से अधिक तत्वों के साथ।)

जुड़े हुए प्रश्न के मेरे उत्तर का तर्क यह दर्शाता है कि दोनों $\mathsf{SAT}$ को कम करता है $\Sigma_1$ इस समस्या का टुकड़ा: प्रस्ताव वाक्य को बदलने का एक कुशल तरीका है $\varphi$ पहले क्रम के वाक्य में $\hat{\varphi}$ ऐसा है कि ${\bf 2}\models\hat{\varphi}$ iff $\varphi$संतोषजनक है। निश्चित रूप से इसका मतलब है कि$\mathsf{coSAT}$ को कम करता है $\Pi_1$ टुकड़ा।

क्वांटिफायर को जोड़ने के व्यवहार को देखते हुए, एक उत्तर में एक स्वाभाविक अनुमान यह है कि यह बहुपद पदानुक्रम में स्तरों के बिल्कुल मेल होना चाहिए, लेकिन मैं तुरंत विवरण नहीं देखता हूं।

Answer 1

यह देखते हुए कि क्वांटिफाइड बुलियन फॉर्मूले PSPACE- पूर्ण हैं और इसे शुद्ध प्रथम-क्रम सिद्धांत में घटाया जा सकता है $2$, यह PSPACE- कठिन है। दूसरी ओर, यह स्पष्ट रूप से PSPACE में है (चूंकि स्पष्ट पुनरावर्ती एल्गोरिथ्म अंतरिक्ष उपयोग में बहुपद है)। तो यह PSPACE- पूर्ण है।