पीस्पेस: Difference between revisions

From Vigyanwiki
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|computer science|{{tmath|\mathsf{P \overset{?}{{=}} PSPACE} }}}}
{{unsolved|कंप्यूटर विज्ञान|{{tmath|\mathsf{P \overset{?}{{=}} PSPACE} }}}}
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, पीएसपीएसीई सभी [[निर्णय समस्या]]ओं का सेट है जिसे [[बहुपद]] [[अंतरिक्ष जटिलता]] का उपयोग करके [[ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है।
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''पीस्पेस''' सभी [[निर्णय समस्या]]ओं का समुच्च्य है जिसे [[बहुपद]] [[अंतरिक्ष जटिलता|समिष्ट जटिलता]] का उपयोग करके [[ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है।


== औपचारिक परिभाषा ==
== औपचारिक परिभाषा ==
यदि हम SPACE(f(n)) द्वारा निरूपित करते हैं, तो इनपुट आकार n के कुछ फ़ंक्शन f के लिए O(f(n)) स्पेस का उपयोग करके [[ ट्यूरिंग मशीनें |ट्यूरिंग मशीनें]] द्वारा हल की जा सकने वाली सभी समस्याओं का सेट, तो हम PSPACE को औपचारिक रूप से परिभाषित कर सकते हैं<ref name=AB81>Arora & Barak (2009) p.81</ref>
यदि हम स्पेस(f(n)) द्वारा निरूपित करते हैं, जिससे इनपुट आकार n के कुछ फलन f के लिए O(f(n)) स्पेस का उपयोग करके [[ ट्यूरिंग मशीनें |ट्यूरिंग मशीनें]] द्वारा हल की जा सकने वाली सभी समस्याओं का समुच्च्य, तो हम पीस्पेस को औपचारिक रूप से परिभाषित कर सकते हैं <ref name=AB81>Arora & Barak (2009) p.81</ref>
:<math>\mathsf{PSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{SPACE}(n^k). </math>
:<math>\mathsf{PSPACE} = \bigcup_{k\in\mathbb{N}} \mathsf{SPACE}(n^k). </math>
PSPACE [[संदर्भ-संवेदनशील भाषा]]ओं के सेट का सख्त सुपरसेट है।
पीस्पेस [[संदर्भ-संवेदनशील भाषा]]ओं के समुच्च्य का कठिन सुपरसेट है।


यह पता चला है कि ट्यूरिंग मशीन को [[गैर-नियतात्मक एल्गोरिथ्म]] की अनुमति देने से कोई अतिरिक्त शक्ति नहीं जुड़ती है। सैविच के प्रमेय के कारण,<ref name=AB85>Arora & Barak (2009) p.85</ref> एनपीपीएसीईई पीएसपीएसीई के समतुल्य है, अनिवार्य रूप से क्योंकि नियतात्मक ट्यूरिंग मशीन अधिक स्थान की आवश्यकता के बिना [[गैर-नियतात्मक ट्यूरिंग मशीन]] का अनुकरण कर सकती है (भले ही [[पी बनाम एनपी समस्या]] हो)।<ref name=AB86>Arora & Barak (2009) p.86</ref> साथ ही, पीएसपीएसीई में सभी समस्याओं का [[पूरक (जटिलता)]] भी पीएसपीएसीई में है, जिसका अर्थ है कि सह-पीएसपीएसीई {{=}} पीस्पेस.
यह पता चला है कि ट्यूरिंग मशीन को [[गैर-नियतात्मक एल्गोरिथ्म]] की अनुमति देने से कोई अतिरिक्त शक्ति नहीं जुड़ती है। सैविच के प्रमेय के कारण,<ref name=AB85>Arora & Barak (2009) p.85</ref> एनपीपीएसीईई पीस्पेस के समतुल्य है, अनिवार्य रूप से क्योंकि नियतात्मक ट्यूरिंग मशीन अधिक स्थान की आवश्यकता के बिना [[गैर-नियतात्मक ट्यूरिंग मशीन]] का अनुकरण कर सकती है (तथापि [[पी बनाम एनपी समस्या]] हो)।<ref name=AB86>Arora & Barak (2009) p.86</ref> साथ ही, पीस्पेस में सभी समस्याओं का [[पूरक (जटिलता)|पूरक]]   भी पीस्पेस में है, जिसका अर्थ है कि सह-पीस्पेस {{=}} पीस्पेस.


==अन्य वर्गों के बीच संबंध==
==अन्य वर्गों के बीच संबंध==
[[Image:Complexity subsets pspace.svg|300px|thumb|right|जटिलता वर्गों के बीच संबंध का प्रतिनिधित्व]]PSPACE और जटिलता वर्गों NL (जटिलता), P (जटिलता), NP (जटिलता), PH (जटिलता), [[EXPTIME]] और [[EXPSPACE]] के बीच निम्नलिखित संबंध ज्ञात हैं (ध्यान दें कि ⊊, जिसका अर्थ है सख्त रोकथाम, ⊈ के समान नहीं है) :
[[Image:Complexity subsets pspace.svg|300px|thumb|right|जटिलता वर्गों के बीच संबंध का प्रतिनिधित्व]]पीस्पेस और जटिलता वर्गों NL , P , NP , PH , [[EXPTIME]] और [[EXPSPACE]] के बीच निम्नलिखित संबंध ज्ञात हैं (ध्यान दें कि ⊊, जिसका अर्थ है कठिन रोकथाम, ⊈ के समान नहीं है) :


:<math>\begin{array}{l}
:<math>\begin{array}{l}
Line 19: Line 19:
\mathsf{NL \subsetneq PSPACE \subsetneq EXPSPACE}\\
\mathsf{NL \subsetneq PSPACE \subsetneq EXPSPACE}\\
\mathsf{P\subsetneq EXPTIME}\end{array}</math>
\mathsf{P\subsetneq EXPTIME}\end{array}</math>
तीसरी पंक्ति से, यह पता चलता है कि पहली और दूसरी पंक्ति दोनों में, सेट की कम से कम रोकथाम सख्त होनी चाहिए, लेकिन यह ज्ञात नहीं है कि कौन सी है। यह व्यापक रूप से संदेह है कि सभी सख्त हैं।
तीसरी पंक्ति से, यह पता चलता है कि पहली और दूसरी पंक्ति दोनों में, समुच्च्य की कम से कम रोकथाम कठिन होनी चाहिए, किन्तु यह ज्ञात नहीं है कि कौन c है। यह व्यापक रूप से संदेह है कि सभी कठिन हैं।


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


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


== समापन गुण ==
== समापन गुण ==
क्लास पीएसपीएसीई ऑपरेशन [[ संघ (सेट सिद्धांत) |संघ (सेट सिद्धांत)]] , [[ पूरक (सेट सिद्धांत) |पूरक (सेट सिद्धांत)]] , और [[क्लेन स्टार]] के तहत बंद है।
क्लास पीस्पेस संचालन [[ संघ (सेट सिद्धांत) |यूनियन (समुच्च्य सिद्धांत)]] , [[ पूरक (सेट सिद्धांत) |पूरक (समुच्च्य सिद्धांत)]] , और [[क्लेन स्टार]] के अनुसार विवृत है।


== अन्य लक्षण ==
== अन्य लक्षण ==
PSPACE का वैकल्पिक लक्षण वर्णन बहुपद समय में [[वैकल्पिक ट्यूरिंग मशीन]] द्वारा तय की जाने वाली समस्याओं का समूह है, जिसे कभी-कभी APTIME या सिर्फ AP भी कहा जाता है।<ref name=AB100>Arora & Barak (2009) p.100</ref>
पीस्पेस का वैकल्पिक लक्षण वर्णन बहुपद समय में [[वैकल्पिक ट्यूरिंग मशीन]] द्वारा तय की जाने वाली समस्याओं का समूह है, जिसे कभी-कभी APTIME या सिर्फ AP भी कहा जाता है।<ref name=AB100>Arora & Barak (2009) p.100</ref>[[वर्णनात्मक जटिलता]] सिद्धांत से पीस्पेस का तार्किक लक्षण वर्णन यह है कि यह ट्रांजिटिव क्लोजर संचालक के अतिरिक्त के साथ दूसरे क्रम के तर्क में व्यक्त की जाने वाली समस्याओं का समुच्च्य है। पूर्ण [[सकर्मक समापन]] की आवश्यकता नहीं है; क्रमविनिमेय सकर्मक समापन और यहां तक ​​कि अशक्त रूप भी पर्याप्त हैं। यह इस संचालक का जोड़ है जो (संभवतः) पीस्पेस को PH   से अलग करता है।
[[वर्णनात्मक जटिलता]] सिद्धांत से पीएसपीएसीई का तार्किक लक्षण वर्णन यह है कि यह ट्रांजिटिव क्लोजर ऑपरेटर के अतिरिक्त के साथ दूसरे क्रम के तर्क में व्यक्त की जाने वाली समस्याओं का सेट है। पूर्ण [[सकर्मक समापन]] की आवश्यकता नहीं है; क्रमविनिमेय सकर्मक समापन और यहां तक ​​कि कमजोर रूप भी पर्याप्त हैं। यह इस ऑपरेटर का जोड़ है जो (संभवतः) PSPACE को PH (जटिलता) से अलग करता है।


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


PSPACE को क्वांटम जटिलता वर्ग QIP (जटिलता) के रूप में वर्णित किया जा सकता है।<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>
पीस्पेस को क्वांटम जटिलता वर्ग क्यूआईपी  के रूप में वर्णित किया जा सकता है।<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>
PSPACE भी 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> साथ ही बीक्यूपी को भी<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|PSPACE-complete}}
{{main|पीस्पेस: पूर्ण}}
एक भाषा बी पीएसपीएसीई-पूर्ण है यदि यह पीएसपीएसीई में है और यह पीएसपीएसीई-हार्ड है, जिसका अर्थ सभी ए ∈ पीएसपीएसीई के लिए है, <math>A \leq_\text{P} B</math>, कहाँ <math>A \leq_\text{P} B</math> इसका मतलब है कि ए से बी तक [[बहुपद-समय अनेक-एक कमी]] है। पीएसपीएसीई-पूर्ण समस्याएं पीएसपीएसीई समस्याओं का अध्ययन करने के लिए बहुत महत्वपूर्ण हैं क्योंकि वे पीएसपीएसीई में सबसे कठिन समस्याओं का प्रतिनिधित्व करते हैं। पीएसपीएसीई-पूर्ण समस्या का सरल समाधान ढूंढने का मतलब यह होगा कि हमारे पास पीएसपीएसीई में अन्य सभी समस्याओं का सरल समाधान है क्योंकि सभी पीएसपीएसीई समस्याओं को पीएसपीएसीई-पूर्ण समस्या में कम किया जा सकता है।<ref name=AB83>Arora & Barak (2009) p.83</ref>
 
PSPACE-पूर्ण समस्या का उदाहरण [[परिमाणित बूलियन सूत्र समस्या]] है (आमतौर पर इसे QBF या TQBF के रूप में संक्षिप्त किया जाता है; T का अर्थ सत्य है)।<ref name=AB83/>
एक भाषा बी पीस्पेस-पूर्ण है यदि यह पीस्पेस में है और यह पीस्पेस-हार्ड है, जिसका अर्थ सभी ए ∈ पीस्पेस के लिए है, <math>A \leq_\text{P} B</math>, कहाँ <math>A \leq_\text{P} B</math> इसका मतलब है कि ए से बी तक [[बहुपद-समय अनेक-एक कमी]] है। पीस्पेस-पूर्ण समस्याएं पीस्पेस समस्याओं का अध्ययन करने के लिए बहुत महत्वपूर्ण हैं क्योंकि वे पीस्पेस में सबसे कठिन समस्याओं का प्रतिनिधित्व करते हैं। पीस्पेस-पूर्ण समस्या का सरल समाधान ढूंढने का मतलब यह होगा कि हमारे पास पीस्पेस में अन्य सभी समस्याओं का सरल समाधान है क्योंकि सभी पीस्पेस समस्याओं को पीस्पेस-पूर्ण समस्या में कम किया जा सकता है।<ref name=AB83>Arora & Barak (2009) p.83</ref>
पीस्पेस-पूर्ण समस्या का उदाहरण [[परिमाणित बूलियन सूत्र समस्या]] है (आमतौर पर इसे QBF या TQBF के रूप में संक्षिप्त किया जाता है; T का अर्थ सत्य है)।<ref name=AB83/>




Line 50: Line 49:
== संदर्भ ==
== संदर्भ ==
* {{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 }}
* {{cite book | author-link = Michael Sipser | first = Michael | last = Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url-access = registration | url = https://archive.org/details/introductiontoth00sips }} Section 8.2–8.3 (The Class PSPACE, PSPACE-completeness), pp.&nbsp;281–294.
* {{cite book | author-link = Michael Sipser | first = Michael | last = Sipser | year = 1997 | title = Introduction to the Theory of Computation | publisher = PWS Publishing | isbn = 0-534-94728-X | url-access = registration | url = https://archive.org/details/introductiontoth00sips }} Section 8.2–8.3 (The Class पीस्पेस, पीस्पेस-completeness), pp.&nbsp;281–294.
* {{cite book|author-link = Christos Papadimitriou | first=Christos | last=Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1}} Chapter 19: Polynomial space, pp.&nbsp;455–490.
* {{cite book|author-link = Christos Papadimitriou | first=Christos | last=Papadimitriou | year = 1993 | title = Computational Complexity | publisher = Addison Wesley | edition = 1st | isbn = 0-201-53082-1}} Chapter 19: Polynomial स्पेस, pp.&nbsp;455–490.
* {{cite book| first = Michael | last=Sipser | author-link = Michael Sipser | year = 2006 | title = Introduction to the Theory of Computation | publisher = Thomson Course Technology| edition = 2nd | isbn = 0-534-95097-3}} Chapter 8: Space Complexity
* {{cite book| first = Michael | last=Sipser | author-link = Michael Sipser | year = 2006 | title = Introduction to the Theory of Computation | publisher = Thomson Course Technology| edition = 2nd | isbn = 0-534-95097-3}} Chapter 8: स्पेस Complexity
* {{CZoo|PSPACE|P#pspace}}
* {{CZoo|PSPACE|P#pspace}}


Revision as of 14:26, 15 July 2023

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

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

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

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

यदि हम स्पेस(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]


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

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

एक भाषा बी पीस्पेस-पूर्ण है यदि यह पीस्पेस में है और यह पीस्पेस-हार्ड है, जिसका अर्थ सभी ए ∈ पीस्पेस के लिए है, , कहाँ इसका मतलब है कि ए से बी तक बहुपद-समय अनेक-एक कमी है। पीस्पेस-पूर्ण समस्याएं पीस्पेस समस्याओं का अध्ययन करने के लिए बहुत महत्वपूर्ण हैं क्योंकि वे पीस्पेस में सबसे कठिन समस्याओं का प्रतिनिधित्व करते हैं। पीस्पेस-पूर्ण समस्या का सरल समाधान ढूंढने का मतलब यह होगा कि हमारे पास पीस्पेस में अन्य सभी समस्याओं का सरल समाधान है क्योंकि सभी पीस्पेस समस्याओं को पीस्पेस-पूर्ण समस्या में कम किया जा सकता है।[8] पीस्पेस-पूर्ण समस्या का उदाहरण परिमाणित बूलियन सूत्र समस्या है (आमतौर पर इसे QBF या TQBF के रूप में संक्षिप्त किया जाता है; T का अर्थ सत्य है)।[8]


टिप्पणियाँ

  1. ↑ Arora & Barak (2009) p.81
  2. ↑ Arora & Barak (2009) p.85
  3. ↑ Arora & Barak (2009) p.86
  4. ↑ Arora & Barak (2009) p.100
  5. ↑ Rahul Jain; Zhengfeng Ji; Sarvagya Upadhyay; John Watrous (July 2009). "QIP = PSPACE". arXiv:0907.4737 [quant-ph].
  6. ↑ S. Aaronson (March 2005). "एनपी-संपूर्ण समस्याएं और भौतिक वास्तविकता". SIGACT News. arXiv:quant-ph/0502072. Bibcode:2005quant.ph..2072A. doi:10.1145/1052796.1052804. S2CID 18759797..
  7. ↑ 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. ↑ 8.0 8.1 Arora & Barak (2009) p.83


संदर्भ

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=पीस्पेस&oldid=222988’