2-एक्सप्टिटाइम: Difference between revisions
From Vigyanwiki
(Created page with "कम्प्यूटेशनल जटिलता सिद्धांत में, जटिलता वर्ग 2-EXPTIME (कभी-कभी 2-EXP भी...") |
(text) |
||
| Line 1: | Line 1: | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, [[जटिलता वर्ग]] 2- | [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, [[जटिलता वर्ग]] '''2-एक्सप्टिटाइम''' (कभी-कभी 2-ईएक्सपी भी कहा जाता है) बड़े O(2<sup>2''p''(''n'')</sup>) समय नोटेशन में एक [[नियतात्मक ट्यूरिंग मशीन]] द्वारा हल करने योग्य सभी [[निर्णय समस्या]]ओं का [[सेट (गणित)|सम्मुच्चय (गणित)]] है, जहां p(n) n का एक बहुपद फलन है। | ||
[[DTIME]] के संदर्भ में, | [[DTIME|डीटाइम]] के संदर्भ में, | ||
:<math> \mathsf{2\mbox{-}EXPTIME} = \bigcup_{k \in \mathbb{N} } \mathsf{ DTIME } \left( 2^{ 2^{n^k} } \right) . </math> | :<math> \mathsf{2\mbox{-}EXPTIME} = \bigcup_{k \in \mathbb{N} } \mathsf{ DTIME } \left( 2^{ 2^{n^k} } \right) . </math> | ||
हम जानते हैं | हम जानते हैं | ||
:P (जटिलता) ⊆ [[एन[[पी (जटिलता)]]]] ⊆ [[PSPACE]] ⊆ [[EXPTIME]] ⊆ [[NEXPTIME]] ⊆ | :P (जटिलता) ⊆ [[एन[[पी (जटिलता)]]]] ⊆ [[PSPACE|पीएसपीएसीई]] ⊆ [[EXPTIME|एक्सप्टिटाइम]] ⊆ [[NEXPTIME|Nएक्सप्टिटाइम]] ⊆ एक्सप्टिटाइम ⊆ 2-एक्सप्टिटाइम ⊆ [[प्राथमिक]]। | ||
2- | 2-एक्सप्टिटाइम को स्पेस क्लास [[PSPACE|ए]][[EXPSPACE|ईएक्सपीएसपीएसीई]] के रूप में भी दोबारा तैयार किया जा सकता है, ये समस्याएं एक्सपोनेंशियल स्पेस में एक [[वैकल्पिक ट्यूरिंग मशीन]] द्वारा हल की जा सकती हैं। यह देखने का एक तरीका है कि ईएक्सपीएसपीएसीई ⊆ 2-एक्सप्टिटाइम, क्योंकि एक वैकल्पिक ट्यूरिंग मशीन कम से कम एक नियतात्मक ट्यूरिंग मशीन जितनी शक्तिशाली होती है। <ref>[[Christos Papadimitriou]], Computational Complexity (1994), {{isbn|978-0-201-53082-7}}. Section 20.1, corollary 3, page 495.</ref> | ||
2- | |||
2-एक्सप्टिटाइम जटिलता वर्गों के पदानुक्रम में एक वर्ग है जिसकी समय सीमा लगातार बढ़ती जा रही है। कक्षा 3-एक्सप्टिटाइम को 2-एक्सप्टिटाइम के समान ही परिभाषित किया गया है, लेकिन तीन गुना घातीय समय सीमा के साथ <math>2^{2^{2^{n^k}}}</math>है। इसे उच्चतर और उच्च समय सीमा के लिए सामान्यीकृत किया जा सकता है। | |||
==उदाहरण== | ==उदाहरण== | ||
कलन विधि के उदाहरण जिनमें कम से कम 2-एक्सप्टिटाइम की आवश्यकता होती है उनमें निम्न सम्मिलित हैं: | |||
* [[प्रेस्बर्गर अंकगणित]] के लिए प्रत्येक निर्णय प्रक्रिया के लिए कम से कम दोगुना घातीय समय की आवश्यकता होती है<ref>[[Michael J. Fischer|Fischer, M. J.]], and [[Michael O. Rabin]], 1974, "[http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps "Super-Exponential Complexity of Presburger Arithmetic.] {{Webarchive|url=https://web.archive.org/web/20060915010325/http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps |date=2006-09-15 }}" ''Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7'': 27–41</ref> | * [[प्रेस्बर्गर अंकगणित]] के लिए प्रत्येक निर्णय प्रक्रिया के लिए कम से कम दोगुना घातीय समय की आवश्यकता होती है <ref>[[Michael J. Fischer|Fischer, M. J.]], and [[Michael O. Rabin]], 1974, "[http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps "Super-Exponential Complexity of Presburger Arithmetic.] {{Webarchive|url=https://web.archive.org/web/20060915010325/http://www.lcs.mit.edu/publications/pubs/ps/MIT-LCS-TM-043.ps |date=2006-09-15 }}" ''Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7'': 27–41</ref> | ||
* किसी क्षेत्र पर ग्रोबनेर आधार की गणना करना। सबसे खराब स्थिति में, ग्रोबनेर आधार में कई तत्व हो सकते हैं जो चर की संख्या में दोगुना घातीय है। दूसरी ओर, ग्रोबनेर आधार | * किसी क्षेत्र पर ग्रोबनेर आधार की गणना करना। सबसे खराब स्थिति में, ग्रोबनेर आधार में कई तत्व हो सकते हैं जो चर की संख्या में दोगुना घातीय है। दूसरी ओर, ग्रोबनेर आधार कलन विधि की सबसे खराब स्थिति की जटिलता चर की संख्या के साथ-साथ प्रवेश आकार में दोगुनी घातीय है। <ref>{{cite journal |last1=Dubé |first1=Thomas W. |title=The Structure of Polynomial Ideals and Gröbner Bases |journal=[[SIAM Journal on Computing]] |date=August 1990 |volume=19 |issue=4 |pages=750–773 |doi=10.1137/0219053}}</ref> | ||
* साहचर्य-कम्यूटेटिव एकीकरणकर्ताओं का एक पूरा | * साहचर्य-कम्यूटेटिव एकीकरणकर्ताओं का एक पूरा सम्मुच्चय ढूँढना है <ref>{{citation | ||
| last1 = Kapur | first1 = Deepak | | last1 = Kapur | first1 = Deepak | ||
| last2 = Narendran | first2 = Paliath | | last2 = Narendran | first2 = Paliath | ||
| Line 26: | Line 27: | ||
| isbn = 0-8186-2735-2| s2cid = 206437926 | | isbn = 0-8186-2735-2| s2cid = 206437926 | ||
}}.</ref> | }}.</ref> | ||
* संतोषजनक सं[[गणना वृक्ष तर्क]]<sup>+</sup> (जो वास्तव में, 2- | * संतोषजनक सं[[गणना वृक्ष तर्क]]<sup>+</sup> है (जो वास्तव में, 2-एक्सप्टिटाइम-पूर्ण है) <ref>{{citation | ||
| last1 = Johannsen | | last1 = Johannsen | ||
| first1 = Jan | | first1 = Jan | ||
| Line 57: | Line 58: | ||
}}.</ref> | }}.</ref> | ||
* [[वास्तविक बंद क्षेत्र]]ों पर क्वांटिफायर उन्मूलन में दोगुना घातीय समय लगता है ([[बेलनाकार बीजगणितीय अपघटन]] देखें)। | * [[वास्तविक बंद क्षेत्र]]ों पर क्वांटिफायर उन्मूलन में दोगुना घातीय समय लगता है ([[बेलनाकार बीजगणितीय अपघटन]] देखें)। | ||
* [[नियमित अभिव्यक्ति]] के [[पूरक (सेट सिद्धांत)]] की गणना करना<ref>{{cite conference | * [[नियमित अभिव्यक्ति]] के [[पूरक (सेट सिद्धांत)|पूरक (सम्मुच्चय सिद्धांत)]] की गणना करना है <ref>{{cite conference | ||
| last1 = Gruber | first1 = Hermann | | last1 = Gruber | first1 = Hermann | ||
| last2 = Holzer | first2 = Markus | | last2 = Holzer | first2 = Markus | ||
| Line 72: | Line 73: | ||
==2-एक्सप्टिटाइम-पूर्ण समस्याएँ== | ==2-एक्सप्टिटाइम-पूर्ण समस्याएँ== | ||
कई पूर्णतः अवलोकनीय खेलों के सामान्यीकरण | कई पूर्णतः अवलोकनीय खेलों के सामान्यीकरण एक्सप्टिटाइम-पूर्ण हैं। इन खेलों को स्तिथि चर और कार्यों/घटनाओं के एक सम्मुच्चय के संदर्भ में परिभाषित संक्रमण प्रणालियों के एक वर्ग के विशेष उदाहरणों के रूप में देखा जा सकता है जो स्तिथि चर के मूल्यों को बदलते हैं, साथ ही इस सवाल के साथ कि क्या [[जीतने की रणनीति]] उपस्थित है। पूरी तरह से अवलोकन योग्य समस्याओं के इस वर्ग का आंशिक रूप से अवलोकन योग्य प्रणालियों में सामान्यीकरण, जटिलता को एक्सप्टिटाइम-पूर्ण से 2-एक्सप्टिटाइम-पूर्ण तक बढ़ा देता है। <ref>{{ cite journal | author = Jussi Rintanen | title = आंशिक अवलोकन के साथ योजना की जटिलता| journal = Proceedings of International Conference on Automated Planning and Scheduling | publisher = AAAI Press | pages = 345–354 | year = 2004 | url=http://www.informatik.uni-freiburg.de/~ki/papers/Rintanen03compl.pdf}}</ref> | ||
Revision as of 06:35, 4 July 2023
कम्प्यूटेशनल जटिलता सिद्धांत में, जटिलता वर्ग 2-एक्सप्टिटाइम (कभी-कभी 2-ईएक्सपी भी कहा जाता है) बड़े O(22p(n)) समय नोटेशन में एक नियतात्मक ट्यूरिंग मशीन द्वारा हल करने योग्य सभी निर्णय समस्याओं का सम्मुच्चय (गणित) है, जहां p(n) n का एक बहुपद फलन है।
डीटाइम के संदर्भ में,
हम जानते हैं
- P (जटिलता) ⊆ [[एनपी (जटिलता)]] ⊆ पीएसपीएसीई ⊆ एक्सप्टिटाइम ⊆ Nएक्सप्टिटाइम ⊆ एक्सप्टिटाइम ⊆ 2-एक्सप्टिटाइम ⊆ प्राथमिक।
2-एक्सप्टिटाइम को स्पेस क्लास एईएक्सपीएसपीएसीई के रूप में भी दोबारा तैयार किया जा सकता है, ये समस्याएं एक्सपोनेंशियल स्पेस में एक वैकल्पिक ट्यूरिंग मशीन द्वारा हल की जा सकती हैं। यह देखने का एक तरीका है कि ईएक्सपीएसपीएसीई ⊆ 2-एक्सप्टिटाइम, क्योंकि एक वैकल्पिक ट्यूरिंग मशीन कम से कम एक नियतात्मक ट्यूरिंग मशीन जितनी शक्तिशाली होती है। [1]
2-एक्सप्टिटाइम जटिलता वर्गों के पदानुक्रम में एक वर्ग है जिसकी समय सीमा लगातार बढ़ती जा रही है। कक्षा 3-एक्सप्टिटाइम को 2-एक्सप्टिटाइम के समान ही परिभाषित किया गया है, लेकिन तीन गुना घातीय समय सीमा के साथ है। इसे उच्चतर और उच्च समय सीमा के लिए सामान्यीकृत किया जा सकता है।
उदाहरण
कलन विधि के उदाहरण जिनमें कम से कम 2-एक्सप्टिटाइम की आवश्यकता होती है उनमें निम्न सम्मिलित हैं:
- प्रेस्बर्गर अंकगणित के लिए प्रत्येक निर्णय प्रक्रिया के लिए कम से कम दोगुना घातीय समय की आवश्यकता होती है [2]
- किसी क्षेत्र पर ग्रोबनेर आधार की गणना करना। सबसे खराब स्थिति में, ग्रोबनेर आधार में कई तत्व हो सकते हैं जो चर की संख्या में दोगुना घातीय है। दूसरी ओर, ग्रोबनेर आधार कलन विधि की सबसे खराब स्थिति की जटिलता चर की संख्या के साथ-साथ प्रवेश आकार में दोगुनी घातीय है। [3]
- साहचर्य-कम्यूटेटिव एकीकरणकर्ताओं का एक पूरा सम्मुच्चय ढूँढना है [4]
- संतोषजनक संगणना वृक्ष तर्क+ है (जो वास्तव में, 2-एक्सप्टिटाइम-पूर्ण है) [5]
- वास्तविक बंद क्षेत्रों पर क्वांटिफायर उन्मूलन में दोगुना घातीय समय लगता है (बेलनाकार बीजगणितीय अपघटन देखें)।
- नियमित अभिव्यक्ति के पूरक (सम्मुच्चय सिद्धांत) की गणना करना है [6]
2-एक्सप्टिटाइम-पूर्ण समस्याएँ
कई पूर्णतः अवलोकनीय खेलों के सामान्यीकरण एक्सप्टिटाइम-पूर्ण हैं। इन खेलों को स्तिथि चर और कार्यों/घटनाओं के एक सम्मुच्चय के संदर्भ में परिभाषित संक्रमण प्रणालियों के एक वर्ग के विशेष उदाहरणों के रूप में देखा जा सकता है जो स्तिथि चर के मूल्यों को बदलते हैं, साथ ही इस सवाल के साथ कि क्या जीतने की रणनीति उपस्थित है। पूरी तरह से अवलोकन योग्य समस्याओं के इस वर्ग का आंशिक रूप से अवलोकन योग्य प्रणालियों में सामान्यीकरण, जटिलता को एक्सप्टिटाइम-पूर्ण से 2-एक्सप्टिटाइम-पूर्ण तक बढ़ा देता है। [7]
यह भी देखें
संदर्भ
- ↑ Christos Papadimitriou, Computational Complexity (1994), ISBN 978-0-201-53082-7. Section 20.1, corollary 3, page 495.
- ↑ Fischer, M. J., and Michael O. Rabin, 1974, ""Super-Exponential Complexity of Presburger Arithmetic. Archived 2006-09-15 at the Wayback Machine" Proceedings of the SIAM-AMS Symposium in Applied Mathematics Vol. 7: 27–41
- ↑ Dubé, Thomas W. (August 1990). "The Structure of Polynomial Ideals and Gröbner Bases". SIAM Journal on Computing. 19 (4): 750–773. doi:10.1137/0219053.
- ↑ Kapur, Deepak; Narendran, Paliath (1992), "Double-exponential complexity of computing a complete set of AC-unifiers", Proc. 7th IEEE Symp. Logic in Computer Science (LICS 1992), pp. 11–21, doi:10.1109/LICS.1992.185515, ISBN 0-8186-2735-2, S2CID 206437926.
- ↑ Johannsen, Jan; Lange, Martin (2003), "CTL+ is complete for double exponential time", in Baeten, Jos C. M.; Lenstra, Jan Karel; Parrow, Joachim; Woeginger, Gerhard J. (eds.), Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003) (PDF), Lecture Notes in Computer Science, vol. 2719, Springer-Verlag, pp. 767–775, doi:10.1007/3-540-45061-0_60, ISBN 978-3-540-40493-4, archived from the original (PDF) on 2007-09-30, retrieved 2006-12-22.
- ↑ Gruber, Hermann; Holzer, Markus (2008). "Finite Automata, Digraph Connectivity, and Regular Expression Size" (PDF). Proceedings of the 35th International Colloquium on Automata, Languages and Programming (ICALP 2008). Vol. 5126. pp. 39–50. doi:10.1007/978-3-540-70583-3_4.
- ↑ Jussi Rintanen (2004). "आंशिक अवलोकन के साथ योजना की जटिलता" (PDF). Proceedings of International Conference on Automated Planning and Scheduling. AAAI Press: 345–354.
