पीस्पेस: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Set of decision problems}} | {{Short description|Set of decision problems}} | ||
[[Image:Complexity-classes-polynomial.svg|thumb|[[पी (जटिलता)|पी]] | [[Image:Complexity-classes-polynomial.svg|thumb|[[पी (जटिलता)|पी]] , [[एनपी (जटिलता)|एनपी]] , [[सह-एनपी]], [[बीपीपी (जटिलता)|बीपीपी]] , पी/पॉली, [[पीएच (जटिलता)|पीएच]] , और पीस्पेस सहित जटिलता वर्गों का समावेश]] | ||
{{unsolved|कंप्यूटर विज्ञान|{{tmath|\mathsf{P \overset{?}{{=}} PSPACE} }}}} | {{unsolved|कंप्यूटर विज्ञान|{{tmath|\mathsf{P \overset{?}{{=}} PSPACE} }}}} | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''पीस्पेस''' सभी [[निर्णय समस्या]]ओं का समुच्च्य है जिसे [[बहुपद]] [[अंतरिक्ष जटिलता|समिष्ट जटिलता]] का उपयोग करके [[ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है। | [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''पीस्पेस''' सभी [[निर्णय समस्या]]ओं का समुच्च्य है जिसे [[बहुपद]] [[अंतरिक्ष जटिलता|समिष्ट जटिलता]] का उपयोग करके [[ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है। | ||
| Line 12: | Line 12: | ||
==अन्य वर्गों के बीच संबंध== | ==अन्य वर्गों के बीच संबंध== | ||
[[Image:Complexity subsets pspace.svg|300px|thumb|right|जटिलता वर्गों के बीच संबंध का प्रतिनिधित्व]]पीस्पेस और जटिलता वर्गों NL , P | [[Image:Complexity subsets pspace.svg|300px|thumb|right|जटिलता वर्गों के बीच संबंध का प्रतिनिधित्व]]पीस्पेस और जटिलता वर्गों NL , P , NP , PH , [[EXPTIME]] और [[EXPSPACE]] के बीच निम्नलिखित संबंध ज्ञात हैं (ध्यान दें कि ⊊, जिसका अर्थ है कठिन रोकथाम, ⊈ के समान नहीं है) : | ||
:<math>\begin{array}{l} | :<math>\begin{array}{l} | ||
| Line 34: | Line 34: | ||
पीस्पेस को क्वांटम जटिलता वर्ग क्यूआईपी के रूप में वर्णित किया जा सकता है।<ref>{{cite arXiv|title=QIP = PSPACE|author1=Rahul Jain|author2=Zhengfeng Ji|author3=Sarvagya Upadhyay|author4-link=John Watrous (computer scientist)|author4=John Watrous|eprint=0907.4737|date=July 2009|class=quant-ph}}</ref> पीस्पेस भी P<sub>CTC</sub> के समान है, इस प्रकार विवृत टाइमलाइक कर्व्स का उपयोग करके मौलिक कंप्यूटरों द्वारा हल की जाने वाली समस्याएं,<ref>{{cite journal|author=S. Aaronson | arxiv=quant-ph/0502072| title= एनपी-संपूर्ण समस्याएं और भौतिक वास्तविकता|journal=SIGACT News|date=March 2005| doi=10.1145/1052796.1052804|bibcode=2005quant.ph..2072A| s2cid=18759797}}.</ref> साथ ही BQP<sub>CTC</sub> को भी बंद टाइमलाइक कर्व्स का उपयोग करके [[ एक कंप्यूटर जितना |एक कंप्यूटर जितना]] द्वारा हल की जाने वाली समस्याएं होती है।<ref>{{cite journal | doi=10.1098/rspa.2008.0350|bibcode = 2009RSPSA.465..631A | title=बंद टाइमलाइक वक्र क्वांटम और शास्त्रीय कंप्यूटिंग को समकक्ष बनाते हैं| year=2009 | last1=Watrous | first1=John | last2=Aaronson | first2=Scott | journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume=465 | issue=2102 | pages=631 |arxiv = 0808.2669 |s2cid = 745646 }}</ref> | पीस्पेस को क्वांटम जटिलता वर्ग क्यूआईपी के रूप में वर्णित किया जा सकता है।<ref>{{cite arXiv|title=QIP = PSPACE|author1=Rahul Jain|author2=Zhengfeng Ji|author3=Sarvagya Upadhyay|author4-link=John Watrous (computer scientist)|author4=John Watrous|eprint=0907.4737|date=July 2009|class=quant-ph}}</ref> पीस्पेस भी P<sub>CTC</sub> के समान है, इस प्रकार विवृत टाइमलाइक कर्व्स का उपयोग करके मौलिक कंप्यूटरों द्वारा हल की जाने वाली समस्याएं,<ref>{{cite journal|author=S. Aaronson | arxiv=quant-ph/0502072| title= एनपी-संपूर्ण समस्याएं और भौतिक वास्तविकता|journal=SIGACT News|date=March 2005| doi=10.1145/1052796.1052804|bibcode=2005quant.ph..2072A| s2cid=18759797}}.</ref> साथ ही BQP<sub>CTC</sub> को भी बंद टाइमलाइक कर्व्स का उपयोग करके [[ एक कंप्यूटर जितना |एक कंप्यूटर जितना]] द्वारा हल की जाने वाली समस्याएं होती है।<ref>{{cite journal | doi=10.1098/rspa.2008.0350|bibcode = 2009RSPSA.465..631A | title=बंद टाइमलाइक वक्र क्वांटम और शास्त्रीय कंप्यूटिंग को समकक्ष बनाते हैं| year=2009 | last1=Watrous | first1=John | last2=Aaronson | first2=Scott | journal=Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences | volume=465 | issue=2102 | pages=631 |arxiv = 0808.2669 |s2cid = 745646 }}</ref> | ||
== पीस्पेस-पूर्णता == | == पीस्पेस-पूर्णता == | ||
{{main|पीस्पेस: पूर्ण}} | {{main|पीस्पेस: पूर्ण}} | ||
एक भाषा B पीस्पेस-पूर्ण है यदि यह पीस्पेस में है और यह पीस्पेस-हार्ड है, जिसका अर्थ सभी A | एक भाषा B पीस्पेस-पूर्ण है यदि यह पीस्पेस में है और यह पीस्पेस-हार्ड है, जिसका अर्थ सभी A ∈ <math>A \leq_\text{P} B</math> पीस्पेस के लिए है, इस प्रकार जहाँ <math>A \leq_\text{P} B</math> इसका कारण है कि A से B तक [[बहुपद-समय अनेक-एक कमी]] है। पीस्पेस-पूर्ण समस्याएं पीस्पेस समस्याओं का अध्ययन करने के लिए बहुत महत्वपूर्ण हैं क्योंकि वे पीस्पेस में सबसे कठिन समस्याओं का प्रतिनिधित्व करते हैं। इस प्रकार पीस्पेस-पूर्ण समस्या का सरल समाधान खोजने का कारण यह होगा कि हमारे पास पीस्पेस में अन्य सभी समस्याओं का सरल समाधान है क्योंकि सभी पीस्पेस समस्याओं को पीस्पेस-पूर्ण समस्या में कम किया जा सकता है।<ref name=AB83>Arora & Barak (2009) p.83</ref> पीस्पेस-पूर्ण समस्या का उदाहरण [[परिमाणित बूलियन सूत्र समस्या]] है (सामान्यतः इसे क्यूबीएफ या टीक्यूबीएफ के रूप में संक्षिप्त किया जाता है; T का अर्थ सत्य है)।<ref name=AB83/> | ||
== टिप्पणियाँ == | == टिप्पणियाँ == | ||
{{reflist}} | {{reflist}} | ||
== संदर्भ == | == संदर्भ == | ||
* {{cite book | zbl=1193.68112 | last1=Arora | first1=Sanjeev | author-link1=Sanjeev Arora | last2=Barak | first2=Boaz | title=Computational complexity. A modern approach | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-42426-4 }} | * {{cite book | zbl=1193.68112 | last1=Arora | first1=Sanjeev | author-link1=Sanjeev Arora | last2=Barak | first2=Boaz | title=Computational complexity. A modern approach | publisher=[[Cambridge University Press]] | year=2009 | isbn=978-0-521-42426-4 }} | ||
Revision as of 14:35, 15 July 2023
कम्प्यूटेशनल जटिलता सिद्धांत में, पीस्पेस सभी निर्णय समस्याओं का समुच्च्य है जिसे बहुपद समिष्ट जटिलता का उपयोग करके ट्यूरिंग मशीन द्वारा हल किया जा सकता है।
औपचारिक परिभाषा
यदि हम स्पेस(f(n)) द्वारा निरूपित करते हैं, जिससे इनपुट आकार n के कुछ फलन f के लिए O(f(n)) स्पेस का उपयोग करके ट्यूरिंग मशीनें द्वारा हल की जा सकने वाली सभी समस्याओं का समुच्च्य, तो हम पीस्पेस को औपचारिक रूप से परिभाषित कर सकते हैं [1]
पीस्पेस संदर्भ-संवेदनशील भाषाओं के समुच्च्य का कठिन सुपरसेट है।
यह पता चला है कि ट्यूरिंग मशीन को गैर-नियतात्मक एल्गोरिथ्म की अनुमति देने से कोई अतिरिक्त शक्ति नहीं जुड़ती है। सैविच के प्रमेय के कारण,[2] एनपीपीएसीईई पीस्पेस के समतुल्य है, अनिवार्य रूप से क्योंकि नियतात्मक ट्यूरिंग मशीन अधिक स्थान की आवश्यकता के बिना गैर-नियतात्मक ट्यूरिंग मशीन का अनुकरण कर सकती है (तथापि पी बनाम एनपी समस्या हो)।[3] साथ ही, पीस्पेस में सभी समस्याओं का पूरक भी पीस्पेस में है, जिसका अर्थ है कि सह-पीस्पेस = पीस्पेस.
अन्य वर्गों के बीच संबंध
पीस्पेस और जटिलता वर्गों NL , P , NP , PH , EXPTIME और EXPSPACE के बीच निम्नलिखित संबंध ज्ञात हैं (ध्यान दें कि ⊊, जिसका अर्थ है कठिन रोकथाम, ⊈ के समान नहीं है) :
तीसरी पंक्ति से, यह पता चलता है कि पहली और दूसरी पंक्ति दोनों में, समुच्च्य की कम से कम रोकथाम कठिन होनी चाहिए, किन्तु यह ज्ञात नहीं है कि कौन c है। यह व्यापक रूप से संदेह है कि सभी कठिन हैं।
तीसरी पंक्ति की रोकथाम दोनों कठिन मानी जाती हैं। पहला प्रत्यक्ष विकर्णीकरण (समिष्ट पदानुक्रम प्रमेय, एनएल ⊊ एनपीस्पेस) और तथ्य यह है कि पीस्पेस से अनुसरण करता है इस प्रकार सेविच = के प्रमेय के माध्यम से एनपीस्पेस दूसरा केवल समिष्ट पदानुक्रम प्रमेय से अनुसरण करता है।
पीस्पेस में सबसे कठिन समस्याएँ पीस्पेस-पूर्ण समस्याएँ हैं। इस प्रकार उन समस्याओं के उदाहरणों के लिए पीस्पेस-पूर्ण देखें जिनके पीस्पेस में होने का संदेह है किन्तु एनपी में नहीं होता है।
समापन गुण
क्लास पीस्पेस संचालन यूनियन (समुच्च्य सिद्धांत) , पूरक (समुच्च्य सिद्धांत) , और क्लेन स्टार के अनुसार विवृत है।
अन्य लक्षण
पीस्पेस का वैकल्पिक लक्षण वर्णन बहुपद समय में वैकल्पिक ट्यूरिंग मशीन द्वारा तय की जाने वाली समस्याओं का समूह है, जिसे कभी-कभी APTIME या सिर्फ AP भी कहा जाता है।[4]वर्णनात्मक जटिलता सिद्धांत से पीस्पेस का तार्किक लक्षण वर्णन यह है कि यह ट्रांजिटिव क्लोजर संचालक के अतिरिक्त के साथ दूसरे क्रम के तर्क में व्यक्त की जाने वाली समस्याओं का समुच्च्य है। पूर्ण सकर्मक समापन की आवश्यकता नहीं है; क्रमविनिमेय सकर्मक समापन और यहां तक कि अशक्त रूप भी पर्याप्त हैं। इस प्रकार यह इस संचालक का जोड़ है जो (संभवतः) पीस्पेस को PH से अलग करता है।
जटिलता सिद्धांत का प्रमुख परिणाम यह है कि पीस्पेस को विशेष इंटरैक्टिव प्रमाण प्रणाली द्वारा पहचाने जाने योग्य सभी भाषाओं के रूप में वर्णित किया जा सकता है, जो क्लास आईपी को परिभाषित करता है। इस प्रणाली में, सर्व-शक्तिशाली कहावत है जो यादृच्छिक बहुपद-समय सत्यापनकर्ता को यह समझाने की प्रयास कर रही है कि भाषा में स्ट्रिंग है। इस प्रकार यदि स्ट्रिंग भाषा में है तो यह सत्यापनकर्ता को उच्च संभावना के साथ समझाने में सक्षम होना चाहिए, किन्तु यदि स्ट्रिंग भाषा में नहीं है तो कम संभावना के अतिरिक्त इसे समझाने में सक्षम नहीं होना चाहिए।
पीस्पेस को क्वांटम जटिलता वर्ग क्यूआईपी के रूप में वर्णित किया जा सकता है।[5] पीस्पेस भी PCTC के समान है, इस प्रकार विवृत टाइमलाइक कर्व्स का उपयोग करके मौलिक कंप्यूटरों द्वारा हल की जाने वाली समस्याएं,[6] साथ ही BQPCTC को भी बंद टाइमलाइक कर्व्स का उपयोग करके एक कंप्यूटर जितना द्वारा हल की जाने वाली समस्याएं होती है।[7]
पीस्पेस-पूर्णता
एक भाषा B पीस्पेस-पूर्ण है यदि यह पीस्पेस में है और यह पीस्पेस-हार्ड है, जिसका अर्थ सभी A ∈ पीस्पेस के लिए है, इस प्रकार जहाँ इसका कारण है कि A से B तक बहुपद-समय अनेक-एक कमी है। पीस्पेस-पूर्ण समस्याएं पीस्पेस समस्याओं का अध्ययन करने के लिए बहुत महत्वपूर्ण हैं क्योंकि वे पीस्पेस में सबसे कठिन समस्याओं का प्रतिनिधित्व करते हैं। इस प्रकार पीस्पेस-पूर्ण समस्या का सरल समाधान खोजने का कारण यह होगा कि हमारे पास पीस्पेस में अन्य सभी समस्याओं का सरल समाधान है क्योंकि सभी पीस्पेस समस्याओं को पीस्पेस-पूर्ण समस्या में कम किया जा सकता है।[8] पीस्पेस-पूर्ण समस्या का उदाहरण परिमाणित बूलियन सूत्र समस्या है (सामान्यतः इसे क्यूबीएफ या टीक्यूबीएफ के रूप में संक्षिप्त किया जाता है; T का अर्थ सत्य है)।[8]
टिप्पणियाँ
- ↑ Arora & Barak (2009) p.81
- ↑ Arora & Barak (2009) p.85
- ↑ Arora & Barak (2009) p.86
- ↑ Arora & Barak (2009) p.100
- ↑ Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (July 2009). "QIP = PSPACE". arXiv:0907.4737 [quant-ph].
- ↑ S. Aaronson (March 2005). "एनपी-संपूर्ण समस्याएं और भौतिक वास्तविकता". SIGACT News. arXiv:quant-ph/0502072. Bibcode:2005quant.ph..2072A. doi:10.1145/1052796.1052804. S2CID 18759797..
- ↑ Watrous, John; Aaronson, Scott (2009). "बंद टाइमलाइक वक्र क्वांटम और शास्त्रीय कंप्यूटिंग को समकक्ष बनाते हैं". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 465 (2102): 631. arXiv:0808.2669. Bibcode:2009RSPSA.465..631A. doi:10.1098/rspa.2008.0350. S2CID 745646.
- ↑ 8.0 8.1 Arora & Barak (2009) p.83
संदर्भ
- 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
