पीस्पेस: Difference between revisions
(Created page with "{{Short description|Set of decision problems}} thumb|[[पी (जटिलता), एनपी (जटिलता), सह...") |
No edit summary |
||
| Line 5: | Line 5: | ||
== औपचारिक परिभाषा == | == औपचारिक परिभाषा == | ||
यदि हम SPACE(f(n)) द्वारा निरूपित करते हैं, तो इनपुट आकार n के कुछ फ़ंक्शन f के लिए O(f(n)) स्पेस का उपयोग करके [[ ट्यूरिंग मशीनें ]] द्वारा हल की जा सकने वाली सभी समस्याओं का सेट, तो हम PSPACE को औपचारिक रूप से परिभाषित कर सकते हैं<ref name=AB81>Arora & Barak (2009) p.81</ref> | यदि हम SPACE(f(n)) द्वारा निरूपित करते हैं, तो इनपुट आकार n के कुछ फ़ंक्शन f के लिए O(f(n)) स्पेस का उपयोग करके [[ ट्यूरिंग मशीनें |ट्यूरिंग मशीनें]] द्वारा हल की जा सकने वाली सभी समस्याओं का सेट, तो हम PSPACE को औपचारिक रूप से परिभाषित कर सकते हैं<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 [[संदर्भ-संवेदनशील भाषा]]ओं के सेट का | PSPACE [[संदर्भ-संवेदनशील भाषा]]ओं के सेट का सख्त सुपरसेट है। | ||
यह पता चला है कि ट्यूरिंग मशीन को [[गैर-नियतात्मक एल्गोरिथ्म]] की अनुमति देने से कोई अतिरिक्त शक्ति नहीं जुड़ती है। सैविच के प्रमेय के कारण,<ref name=AB85>Arora & Barak (2009) p.85</ref> एनपीपीएसीईई पीएसपीएसीई के समतुल्य है, अनिवार्य रूप से क्योंकि | यह पता चला है कि ट्यूरिंग मशीन को [[गैर-नियतात्मक एल्गोरिथ्म]] की अनुमति देने से कोई अतिरिक्त शक्ति नहीं जुड़ती है। सैविच के प्रमेय के कारण,<ref name=AB85>Arora & Barak (2009) p.85</ref> एनपीपीएसीईई पीएसपीएसीई के समतुल्य है, अनिवार्य रूप से क्योंकि नियतात्मक ट्यूरिंग मशीन अधिक स्थान की आवश्यकता के बिना [[गैर-नियतात्मक ट्यूरिंग मशीन]] का अनुकरण कर सकती है (भले ही [[पी बनाम एनपी समस्या]] हो)।<ref name=AB86>Arora & Barak (2009) p.86</ref> साथ ही, पीएसपीएसीई में सभी समस्याओं का [[पूरक (जटिलता)]] भी पीएसपीएसीई में है, जिसका अर्थ है कि सह-पीएसपीएसीई {{=}} पीस्पेस. | ||
==अन्य वर्गों के बीच संबंध== | ==अन्य वर्गों के बीच संबंध== | ||
| 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> | ||
तीसरी पंक्ति से, यह पता चलता है कि पहली और दूसरी पंक्ति दोनों में, सेट की कम से कम | तीसरी पंक्ति से, यह पता चलता है कि पहली और दूसरी पंक्ति दोनों में, सेट की कम से कम रोकथाम सख्त होनी चाहिए, लेकिन यह ज्ञात नहीं है कि कौन सी है। यह व्यापक रूप से संदेह है कि सभी सख्त हैं। | ||
तीसरी पंक्ति की रोकथाम दोनों सख्त मानी जाती हैं। पहला प्रत्यक्ष विकर्णीकरण ([[अंतरिक्ष पदानुक्रम प्रमेय]], एनएल ⊊ एनपीस्पेस) और तथ्य यह है कि पीएसपीएसीई से अनुसरण करता है {{=}} सेविच के प्रमेय के माध्यम से एनपीस्पेस। दूसरा केवल अंतरिक्ष पदानुक्रम प्रमेय से अनुसरण करता है। | तीसरी पंक्ति की रोकथाम दोनों सख्त मानी जाती हैं। पहला प्रत्यक्ष विकर्णीकरण ([[अंतरिक्ष पदानुक्रम प्रमेय]], एनएल ⊊ एनपीस्पेस) और तथ्य यह है कि पीएसपीएसीई से अनुसरण करता है {{=}} सेविच के प्रमेय के माध्यम से एनपीस्पेस। दूसरा केवल अंतरिक्ष पदानुक्रम प्रमेय से अनुसरण करता है। | ||
| Line 26: | Line 26: | ||
== समापन गुण == | == समापन गुण == | ||
क्लास पीएसपीएसीई ऑपरेशन [[ संघ (सेट सिद्धांत) ]], [[ पूरक (सेट सिद्धांत) ]], और [[क्लेन स्टार]] के तहत बंद है। | क्लास पीएसपीएसीई ऑपरेशन [[ संघ (सेट सिद्धांत) |संघ (सेट सिद्धांत)]] , [[ पूरक (सेट सिद्धांत) |पूरक (सेट सिद्धांत)]] , और [[क्लेन स्टार]] के तहत बंद है। | ||
== अन्य लक्षण == | == अन्य लक्षण == | ||
PSPACE का | PSPACE का वैकल्पिक लक्षण वर्णन बहुपद समय में [[वैकल्पिक ट्यूरिंग मशीन]] द्वारा तय की जाने वाली समस्याओं का समूह है, जिसे कभी-कभी APTIME या सिर्फ AP भी कहा जाता है।<ref name=AB100>Arora & Barak (2009) p.100</ref> | ||
[[वर्णनात्मक जटिलता]] सिद्धांत से पीएसपीएसीई का | [[वर्णनात्मक जटिलता]] सिद्धांत से पीएसपीएसीई का तार्किक लक्षण वर्णन यह है कि यह ट्रांजिटिव क्लोजर ऑपरेटर के अतिरिक्त के साथ दूसरे क्रम के तर्क में व्यक्त की जाने वाली समस्याओं का सेट है। पूर्ण [[सकर्मक समापन]] की आवश्यकता नहीं है; क्रमविनिमेय सकर्मक समापन और यहां तक कि कमजोर रूप भी पर्याप्त हैं। यह इस ऑपरेटर का जोड़ है जो (संभवतः) 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> | 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> | ||
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> | 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|PSPACE-complete}} | ||
एक भाषा बी पीएसपीएसीई-पूर्ण है यदि यह पीएसपीएसीई में है और यह पीएसपीएसीई-हार्ड है, जिसका अर्थ सभी ए ∈ पीएसपीएसीई के लिए है, <math>A \leq_\text{P} B</math>, कहाँ <math>A \leq_\text{P} B</math> इसका मतलब है कि ए से बी तक | एक भाषा बी पीएसपीएसीई-पूर्ण है यदि यह पीएसपीएसीई में है और यह पीएसपीएसीई-हार्ड है, जिसका अर्थ सभी ए ∈ पीएसपीएसीई के लिए है, <math>A \leq_\text{P} B</math>, कहाँ <math>A \leq_\text{P} B</math> इसका मतलब है कि ए से बी तक [[बहुपद-समय अनेक-एक कमी]] है। पीएसपीएसीई-पूर्ण समस्याएं पीएसपीएसीई समस्याओं का अध्ययन करने के लिए बहुत महत्वपूर्ण हैं क्योंकि वे पीएसपीएसीई में सबसे कठिन समस्याओं का प्रतिनिधित्व करते हैं। पीएसपीएसीई-पूर्ण समस्या का सरल समाधान ढूंढने का मतलब यह होगा कि हमारे पास पीएसपीएसीई में अन्य सभी समस्याओं का सरल समाधान है क्योंकि सभी पीएसपीएसीई समस्याओं को पीएसपीएसीई-पूर्ण समस्या में कम किया जा सकता है।<ref name=AB83>Arora & Barak (2009) p.83</ref> | ||
PSPACE-पूर्ण समस्या का | PSPACE-पूर्ण समस्या का उदाहरण [[परिमाणित बूलियन सूत्र समस्या]] है (आमतौर पर इसे QBF या TQBF के रूप में संक्षिप्त किया जाता है; T का अर्थ सत्य है)।<ref name=AB83/> | ||
| Line 54: | Line 54: | ||
* {{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: Space Complexity | ||
* {{CZoo|PSPACE|P#pspace}} | * {{CZoo|PSPACE|P#pspace}} | ||
{{DEFAULTSORT:Pspace}}[[Category: जटिलता वर्ग]] | {{DEFAULTSORT:Pspace}}[[Category: जटिलता वर्ग]] | ||
Revision as of 14:10, 15 July 2023
कम्प्यूटेशनल जटिलता सिद्धांत में, पीएसपीएसीई सभी निर्णय समस्याओं का सेट है जिसे बहुपद अंतरिक्ष जटिलता का उपयोग करके ट्यूरिंग मशीन द्वारा हल किया जा सकता है।
औपचारिक परिभाषा
यदि हम SPACE(f(n)) द्वारा निरूपित करते हैं, तो इनपुट आकार n के कुछ फ़ंक्शन f के लिए O(f(n)) स्पेस का उपयोग करके ट्यूरिंग मशीनें द्वारा हल की जा सकने वाली सभी समस्याओं का सेट, तो हम PSPACE को औपचारिक रूप से परिभाषित कर सकते हैं[1]
PSPACE संदर्भ-संवेदनशील भाषाओं के सेट का सख्त सुपरसेट है।
यह पता चला है कि ट्यूरिंग मशीन को गैर-नियतात्मक एल्गोरिथ्म की अनुमति देने से कोई अतिरिक्त शक्ति नहीं जुड़ती है। सैविच के प्रमेय के कारण,[2] एनपीपीएसीईई पीएसपीएसीई के समतुल्य है, अनिवार्य रूप से क्योंकि नियतात्मक ट्यूरिंग मशीन अधिक स्थान की आवश्यकता के बिना गैर-नियतात्मक ट्यूरिंग मशीन का अनुकरण कर सकती है (भले ही पी बनाम एनपी समस्या हो)।[3] साथ ही, पीएसपीएसीई में सभी समस्याओं का पूरक (जटिलता) भी पीएसपीएसीई में है, जिसका अर्थ है कि सह-पीएसपीएसीई = पीस्पेस.
अन्य वर्गों के बीच संबंध
PSPACE और जटिलता वर्गों NL (जटिलता), P (जटिलता), NP (जटिलता), PH (जटिलता), EXPTIME और EXPSPACE के बीच निम्नलिखित संबंध ज्ञात हैं (ध्यान दें कि ⊊, जिसका अर्थ है सख्त रोकथाम, ⊈ के समान नहीं है) :
तीसरी पंक्ति से, यह पता चलता है कि पहली और दूसरी पंक्ति दोनों में, सेट की कम से कम रोकथाम सख्त होनी चाहिए, लेकिन यह ज्ञात नहीं है कि कौन सी है। यह व्यापक रूप से संदेह है कि सभी सख्त हैं।
तीसरी पंक्ति की रोकथाम दोनों सख्त मानी जाती हैं। पहला प्रत्यक्ष विकर्णीकरण (अंतरिक्ष पदानुक्रम प्रमेय, एनएल ⊊ एनपीस्पेस) और तथ्य यह है कि पीएसपीएसीई से अनुसरण करता है = सेविच के प्रमेय के माध्यम से एनपीस्पेस। दूसरा केवल अंतरिक्ष पदानुक्रम प्रमेय से अनुसरण करता है।
PSPACE में सबसे कठिन समस्याएँ PSPACE-पूर्ण समस्याएँ हैं। उन समस्याओं के उदाहरणों के लिए पीएसपीएसीई-पूर्ण देखें जिनके पीएसपीएसीई में होने का संदेह है लेकिन एनपी में नहीं।
समापन गुण
क्लास पीएसपीएसीई ऑपरेशन संघ (सेट सिद्धांत) , पूरक (सेट सिद्धांत) , और क्लेन स्टार के तहत बंद है।
अन्य लक्षण
PSPACE का वैकल्पिक लक्षण वर्णन बहुपद समय में वैकल्पिक ट्यूरिंग मशीन द्वारा तय की जाने वाली समस्याओं का समूह है, जिसे कभी-कभी APTIME या सिर्फ AP भी कहा जाता है।[4] वर्णनात्मक जटिलता सिद्धांत से पीएसपीएसीई का तार्किक लक्षण वर्णन यह है कि यह ट्रांजिटिव क्लोजर ऑपरेटर के अतिरिक्त के साथ दूसरे क्रम के तर्क में व्यक्त की जाने वाली समस्याओं का सेट है। पूर्ण सकर्मक समापन की आवश्यकता नहीं है; क्रमविनिमेय सकर्मक समापन और यहां तक कि कमजोर रूप भी पर्याप्त हैं। यह इस ऑपरेटर का जोड़ है जो (संभवतः) PSPACE को PH (जटिलता) से अलग करता है।
जटिलता सिद्धांत का प्रमुख परिणाम यह है कि पीएसपीएसीई को विशेष इंटरैक्टिव प्रमाण प्रणाली द्वारा पहचाने जाने योग्य सभी भाषाओं के रूप में वर्णित किया जा सकता है, जो क्लास आईपी (जटिलता) को परिभाषित करता है। इस प्रणाली में, सर्व-शक्तिशाली कहावत है जो यादृच्छिक बहुपद-समय सत्यापनकर्ता को यह समझाने की कोशिश कर रही है कि भाषा में स्ट्रिंग है। यदि स्ट्रिंग भाषा में है तो यह सत्यापनकर्ता को उच्च संभावना के साथ समझाने में सक्षम होना चाहिए, लेकिन यदि स्ट्रिंग भाषा में नहीं है तो कम संभावना के अलावा इसे समझाने में सक्षम नहीं होना चाहिए।
PSPACE को क्वांटम जटिलता वर्ग QIP (जटिलता) के रूप में वर्णित किया जा सकता है।[5] PSPACE भी P के बराबर हैCTC, बंद टाइमलाइक कर्व्स का उपयोग करके शास्त्रीय कंप्यूटरों द्वारा हल की जाने वाली समस्याएं,[6] साथ ही बीक्यूपी को भीCTCबंद टाइमलाइक कर्व्स का उपयोग करके एक कंप्यूटर जितना द्वारा हल की जाने वाली समस्याएं।[7]
पीएसपीएसीई-पूर्णता
एक भाषा बी पीएसपीएसीई-पूर्ण है यदि यह पीएसपीएसीई में है और यह पीएसपीएसीई-हार्ड है, जिसका अर्थ सभी ए ∈ पीएसपीएसीई के लिए है, , कहाँ इसका मतलब है कि ए से बी तक बहुपद-समय अनेक-एक कमी है। पीएसपीएसीई-पूर्ण समस्याएं पीएसपीएसीई समस्याओं का अध्ययन करने के लिए बहुत महत्वपूर्ण हैं क्योंकि वे पीएसपीएसीई में सबसे कठिन समस्याओं का प्रतिनिधित्व करते हैं। पीएसपीएसीई-पूर्ण समस्या का सरल समाधान ढूंढने का मतलब यह होगा कि हमारे पास पीएसपीएसीई में अन्य सभी समस्याओं का सरल समाधान है क्योंकि सभी पीएसपीएसीई समस्याओं को पीएसपीएसीई-पूर्ण समस्या में कम किया जा सकता है।[8] PSPACE-पूर्ण समस्या का उदाहरण परिमाणित बूलियन सूत्र समस्या है (आमतौर पर इसे QBF या TQBF के रूप में संक्षिप्त किया जाता है; 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 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
