पीस्पेस

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

Unsolved problem in कंप्यूटर विज्ञान:

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

(more unsolved problems in कंप्यूटर विज्ञान)

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

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

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

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

पीस्पेस संदर्भ-संवेदनशील भाषाओं के समुच्च्य का कठिन सुपरसेट है।

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

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

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

पीस्पेस और जटिलता वर्गों 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}}$

तीसरी पंक्ति से, यह पता चलता है कि पहली और दूसरी पंक्ति दोनों में, समुच्च्य की कम से कम प्रतिबंध कठिन होनी चाहिए, किन्तु यह ज्ञात नहीं है कि कौन c है। यह व्यापक रूप से संदेह है कि सभी कठिन हैं।

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

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

समापन गुण

क्लास पीस्पेस संचालन यूनियन (समुच्च्य सिद्धांत) , पूरक (समुच्च्य सिद्धांत) , और क्लेन स्टार के अनुसार विवृत है।

अन्य लक्षण

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

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

पीस्पेस को क्वांटम जटिलता वर्ग क्यूआईपी के रूप में वर्णित किया जा सकता है। पीस्पेस भी P_CTC के समान है, इस प्रकार विवृत टाइमलाइक कर्व्स का उपयोग करके मौलिक कंप्यूटरों द्वारा हल की जाने वाली समस्याएं, साथ ही BQP_CTC को भी बंद टाइमलाइक कर्व्स का उपयोग करके एक कंप्यूटर जितना द्वारा हल की जाने वाली समस्याएं होती है।

पीस्पेस-पूर्णता

Main article: पीस्पेस: पूर्ण

एक भाषा B पीस्पेस-पूर्ण है यदि यह पीस्पेस में है और यह पीस्पेस-हार्ड है, जिसका अर्थ सभी A ∈ $A\leq _{\text{P}}B$ पीस्पेस के लिए है, इस प्रकार जहाँ $A\leq _{\text{P}}B$ इसका कारण है कि A से B तक बहुपद-समय अनेक-एक कमी है। पीस्पेस-पूर्ण समस्याएं पीस्पेस समस्याओं का अध्ययन करने के लिए बहुत महत्वपूर्ण हैं क्योंकि वे पीस्पेस में सबसे कठिन समस्याओं का प्रतिनिधित्व करते हैं। इस प्रकार पीस्पेस-पूर्ण समस्या का सरल समाधान खोजने का कारण यह होगा कि हमारे पास पीस्पेस में अन्य सभी समस्याओं का सरल समाधान है क्योंकि सभी पीस्पेस समस्याओं को पीस्पेस-पूर्ण समस्या में कम किया जा सकता है। पीस्पेस-पूर्ण समस्या का उदाहरण परिमाणित बूलियन सूत्र समस्या है (सामान्यतः इसे क्यूबीएफ या टीक्यूबीएफ के रूप में संक्षिप्त किया जाता है; 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 पीस्पेस, पीस्पेस-completeness), pp. 281–294.
• Papadimitriou, Christos (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Chapter 19: Polynomial स्पेस, pp. 455–490.
• Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Thomson Course Technology. ISBN 0-534-95097-3. Chapter 8: स्पेस Complexity
• Complexity Zoo: PSPACE