पीस्पेस

पी (जटिलता), एनपी (जटिलता), सह-एनपी, बीपीपी (जटिलता), पी/पॉली, पीएच (जटिलता), और पीएसपीएसीई सहित जटिलता वर्गों का समावेश

Unsolved problem in computer science:

${\mathsf {P{\overset {?}{=}}PSPACE}}$

(more unsolved problems in computer science)

कम्प्यूटेशनल जटिलता सिद्धांत में, पीएसपीएसीई सभी निर्णय समस्याओं का सेट है जिसे बहुपद अंतरिक्ष जटिलता का उपयोग करके ट्यूरिंग मशीन द्वारा हल किया जा सकता है।

औपचारिक परिभाषा

यदि हम SPACE(f(n)) द्वारा निरूपित करते हैं, तो इनपुट आकार n के कुछ फ़ंक्शन f के लिए O(f(n)) स्पेस का उपयोग करके ट्यूरिंग मशीनें द्वारा हल की जा सकने वाली सभी समस्याओं का सेट, तो हम PSPACE को औपचारिक रूप से परिभाषित कर सकते हैं

${\mathsf {PSPACE}}=\bigcup _{k\in \mathbb {N} }{\mathsf {SPACE}}(n^{k}).$

PSPACE संदर्भ-संवेदनशील भाषाओं के सेट का एक सख्त सुपरसेट है।

यह पता चला है कि ट्यूरिंग मशीन को गैर-नियतात्मक एल्गोरिथ्म की अनुमति देने से कोई अतिरिक्त शक्ति नहीं जुड़ती है। सैविच के प्रमेय के कारण, एनपीपीएसीईई पीएसपीएसीई के समतुल्य है, अनिवार्य रूप से क्योंकि एक नियतात्मक ट्यूरिंग मशीन अधिक स्थान की आवश्यकता के बिना एक गैर-नियतात्मक ट्यूरिंग मशीन का अनुकरण कर सकती है (भले ही पी बनाम एनपी समस्या हो)। साथ ही, पीएसपीएसीई में सभी समस्याओं का पूरक (जटिलता) भी पीएसपीएसीई में है, जिसका अर्थ है कि सह-पीएसपीएसीई = पीस्पेस.

अन्य वर्गों के बीच संबंध

जटिलता वर्गों के बीच संबंध का प्रतिनिधित्व

PSPACE और जटिलता वर्गों NL (जटिलता), P (जटिलता), NP (जटिलता), PH (जटिलता), EXPTIME और EXPSPACE के बीच निम्नलिखित संबंध ज्ञात हैं (ध्यान दें कि ⊊, जिसका अर्थ है सख्त रोकथाम, ⊈ के समान नहीं है) :

${\begin{array}{l}{\mathsf {NL\subseteq P\subseteq NP\subseteq PH\subseteq PSPACE}}\\{\mathsf {PSPACE\subseteq EXPTIME\subseteq EXPSPACE}}\\{\mathsf {NL\subsetneq PSPACE\subsetneq EXPSPACE}}\\{\mathsf {P\subsetneq EXPTIME}}\end{array}}$

तीसरी पंक्ति से, यह पता चलता है कि पहली और दूसरी पंक्ति दोनों में, सेट की कम से कम एक रोकथाम सख्त होनी चाहिए, लेकिन यह ज्ञात नहीं है कि कौन सी है। यह व्यापक रूप से संदेह है कि सभी सख्त हैं।

तीसरी पंक्ति की रोकथाम दोनों सख्त मानी जाती हैं। पहला प्रत्यक्ष विकर्णीकरण (अंतरिक्ष पदानुक्रम प्रमेय, एनएल ⊊ एनपीस्पेस) और तथ्य यह है कि पीएसपीएसीई से अनुसरण करता है = सेविच के प्रमेय के माध्यम से एनपीस्पेस। दूसरा केवल अंतरिक्ष पदानुक्रम प्रमेय से अनुसरण करता है।

PSPACE में सबसे कठिन समस्याएँ PSPACE-पूर्ण समस्याएँ हैं। उन समस्याओं के उदाहरणों के लिए पीएसपीएसीई-पूर्ण देखें जिनके पीएसपीएसीई में होने का संदेह है लेकिन एनपी में नहीं।

समापन गुण

क्लास पीएसपीएसीई ऑपरेशन संघ (सेट सिद्धांत) , पूरक (सेट सिद्धांत) , और क्लेन स्टार के तहत बंद है।

अन्य लक्षण

PSPACE का एक वैकल्पिक लक्षण वर्णन बहुपद समय में एक वैकल्पिक ट्यूरिंग मशीन द्वारा तय की जाने वाली समस्याओं का समूह है, जिसे कभी-कभी APTIME या सिर्फ AP भी कहा जाता है। वर्णनात्मक जटिलता सिद्धांत से पीएसपीएसीई का एक तार्किक लक्षण वर्णन यह है कि यह एक ट्रांजिटिव क्लोजर ऑपरेटर के अतिरिक्त के साथ दूसरे क्रम के तर्क में व्यक्त की जाने वाली समस्याओं का सेट है। पूर्ण सकर्मक समापन की आवश्यकता नहीं है; एक क्रमविनिमेय सकर्मक समापन और यहां तक ​​कि कमजोर रूप भी पर्याप्त हैं। यह इस ऑपरेटर का जोड़ है जो (संभवतः) PSPACE को PH (जटिलता) से अलग करता है।

जटिलता सिद्धांत का एक प्रमुख परिणाम यह है कि पीएसपीएसीई को एक विशेष इंटरैक्टिव प्रमाण प्रणाली द्वारा पहचाने जाने योग्य सभी भाषाओं के रूप में वर्णित किया जा सकता है, जो क्लास आईपी (जटिलता) को परिभाषित करता है। इस प्रणाली में, एक सर्व-शक्तिशाली कहावत है जो एक यादृच्छिक बहुपद-समय सत्यापनकर्ता को यह समझाने की कोशिश कर रही है कि भाषा में एक स्ट्रिंग है। यदि स्ट्रिंग भाषा में है तो यह सत्यापनकर्ता को उच्च संभावना के साथ समझाने में सक्षम होना चाहिए, लेकिन यदि स्ट्रिंग भाषा में नहीं है तो कम संभावना के अलावा इसे समझाने में सक्षम नहीं होना चाहिए।

PSPACE को क्वांटम जटिलता वर्ग QIP (जटिलता) के रूप में वर्णित किया जा सकता है। PSPACE भी P के बराबर है_CTC, बंद टाइमलाइक कर्व्स का उपयोग करके शास्त्रीय कंप्यूटरों द्वारा हल की जाने वाली समस्याएं, साथ ही बीक्यूपी को भी_CTCबंद टाइमलाइक कर्व्स का उपयोग करके एक कंप्यूटर जितना द्वारा हल की जाने वाली समस्याएं।

पीएसपीएसीई-पूर्णता

Main article: PSPACE-complete

एक भाषा बी पीएसपीएसीई-पूर्ण है यदि यह पीएसपीएसीई में है और यह पीएसपीएसीई-हार्ड है, जिसका अर्थ सभी ए ∈ पीएसपीएसीई के लिए है, $A\leq _{\text{P}}B$, कहाँ $A\leq _{\text{P}}B$ इसका मतलब है कि ए से बी तक एक बहुपद-समय अनेक-एक कमी है। पीएसपीएसीई-पूर्ण समस्याएं पीएसपीएसीई समस्याओं का अध्ययन करने के लिए बहुत महत्वपूर्ण हैं क्योंकि वे पीएसपीएसीई में सबसे कठिन समस्याओं का प्रतिनिधित्व करते हैं। पीएसपीएसीई-पूर्ण समस्या का एक सरल समाधान ढूंढने का मतलब यह होगा कि हमारे पास पीएसपीएसीई में अन्य सभी समस्याओं का एक सरल समाधान है क्योंकि सभी पीएसपीएसीई समस्याओं को पीएसपीएसीई-पूर्ण समस्या में कम किया जा सकता है। PSPACE-पूर्ण समस्या का एक उदाहरण परिमाणित बूलियन सूत्र समस्या है (आमतौर पर इसे QBF या TQBF के रूप में संक्षिप्त किया जाता है; T का अर्थ सत्य है)।

संदर्भ

• Arora, Sanjeev; Barak, Boaz (2009). Computational complexity. A modern approach. Cambridge University Press. ISBN 978-0-521-42426-4. Zbl 1193.68112.
• Sipser, Michael (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp. 281–294.
• Papadimitriou, Christos (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Chapter 19: Polynomial space, pp. 455–490.
• Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Thomson Course Technology. ISBN 0-534-95097-3. Chapter 8: Space Complexity
• Complexity Zoo: PSPACE