2-एक्सप्टिटाइम: Difference between revisions

From Vigyanwiki
(Created page with "कम्प्यूटेशनल जटिलता सिद्धांत में, जटिलता वर्ग 2-EXPTIME (कभी-कभी 2-EXP भी...")
 
No edit summary
 
(4 intermediate revisions by 4 users not shown)
Line 1: Line 1:
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, [[जटिलता वर्ग]] 2-EXPTIME (कभी-कभी 2-EXP भी कहा जाता है) बड़े O नोटेशन(2) में एक [[नियतात्मक ट्यूरिंग मशीन]] द्वारा हल करने योग्य सभी [[निर्णय समस्या]]ओं का [[सेट (गणित)]] है<sup>2<sup>p(n)</sup></sup>) समय, जहां p(n) n का एक बहुपद फलन है।
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल सम्मिश्रता सिद्धांत]] में, [[जटिलता वर्ग|सम्मिश्रता वर्ग]] '''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]] ⊆ EXPTIME ⊆ 2-EXPTIME ⊆ [[प्राथमिक]]।
:P (सम्मिश्रता) ⊆ NP (सम्मिश्रता) ⊆ पीएसपीएसीई ⊆ [[EXPTIME|एक्सप्टिटाइम]] ⊆ Nएक्सप्टिटाइम ⊆ एक्सप्टिटाइम ⊆ 2-एक्सप्टिटाइम ⊆ [[प्राथमिक]] है।


2-EXPTIME को स्पेस क्लास A[[EXPSPACE]] के रूप में भी दोबारा तैयार किया जा सकता है, ये समस्याएं एक्सपोनेंशियल स्पेस में एक [[वैकल्पिक ट्यूरिंग मशीन]] द्वारा हल की जा सकती हैं। यह देखने का एक तरीका है कि EXPSPACE ⊆ 2-EXPTIME, क्योंकि एक वैकल्पिक ट्यूरिंग मशीन कम से कम एक नियतात्मक ट्यूरिंग मशीन जितनी शक्तिशाली होती है।<ref>[[Christos Papadimitriou]], Computational Complexity (1994), {{isbn|978-0-201-53082-7}}. Section 20.1, corollary 3, page 495.</ref>
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-EXPTIME जटिलता वर्गों के पदानुक्रम में एक वर्ग है जिसकी समय सीमा लगातार बढ़ती जा रही है। कक्षा 3-EXPTIME को 2-EXPTIME के ​​समान ही परिभाषित किया गया है, लेकिन तीन गुना घातीय समय सीमा के साथ <math>2^{2^{2^{n^k}}}</math>. इसे उच्चतर और उच्च समय सीमा के लिए सामान्यीकृत किया जा सकता है।
 
2-एक्सप्टिटाइम सम्मिश्रता वर्गों के पदानुक्रम में एक वर्ग है जिसकी समय सीमा लगातार बढ़ती जा रही है। कक्षा 3-एक्सप्टिटाइम को 2-एक्सप्टिटाइम के ​​समान ही परिभाषित किया गया है, लेकिन तीन गुना घातीय समय सीमा के साथ <math>2^{2^{2^{n^k}}}</math>है। इसे उच्चतर और उच्च समय सीमा के लिए सामान्यीकृत किया जा सकता है।


==उदाहरण==
==उदाहरण==
एल्गोरिदम के उदाहरण जिनमें कम से कम 2-EXPTIME की आवश्यकता होती है उनमें शामिल हैं:
कलन विधि के उदाहरण जिनमें कम से कम 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>{{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
* साहचर्य-कम्यूटेटिव एकीकरणकर्ताओं का एक पूरा सम्मुच्चय ढूँढना है <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-EXPTIME-पूर्ण है)<ref>{{citation
* संतोषजनक सं[[गणना वृक्ष तर्क]]<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-एक्सप्टिटाइम-पूर्ण समस्याएँ==


कई पूर्णतः अवलोकनीय खेलों के सामान्यीकरण EXPTIME-पूर्ण हैं। इन खेलों को राज्य चर और कार्यों/घटनाओं के एक सेट के संदर्भ में परिभाषित संक्रमण प्रणालियों के एक वर्ग के विशेष उदाहरणों के रूप में देखा जा सकता है जो राज्य चर के मूल्यों को बदलते हैं, साथ ही इस सवाल के साथ कि क्या [[जीतने की रणनीति]] मौजूद है। पूरी तरह से अवलोकन योग्य समस्याओं के इस वर्ग का आंशिक रूप से अवलोकन योग्य प्रणालियों में सामान्यीकरण, जटिलता को EXPTIME-पूर्ण से 2-EXPTIME-पूर्ण तक बढ़ा देता है।<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>
कई पूर्णतः अवलोकनीय खेलों के सामान्यीकरण एक्सप्टिटाइम-पूर्ण हैं। इन खेलों को स्तिथि चर और कार्यों/घटनाओं के एक सम्मुच्चय के संदर्भ में परिभाषित संक्रमण प्रणालियों के एक वर्ग के विशेष उदाहरणों के रूप में देखा जा सकता है जो स्तिथि चर के मूल्यों को बदलते हैं, साथ ही इस सवाल के साथ कि क्या [[जीतने की रणनीति]] उपस्थित है। पूरी तरह से अवलोकन योग्य समस्याओं के इस वर्ग का आंशिक रूप से अवलोकन योग्य प्रणालियों में सामान्यीकरण, सम्मिश्रता को एक्सप्टिटाइम-पूर्ण से 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>




Line 81: Line 82:
<references/>
<references/>


{{ComplexityClasses}}
[[Category:Collapse templates]]
[[Category: जटिलता वर्ग]]
 
 
 
[[Category: Machine Translated Page]]
[[Category:Created On 27/06/2023]]
[[Category:Created On 27/06/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Webarchive template wayback links]]
[[Category:Wikipedia metatemplates]]
[[Category:जटिलता वर्ग]]

Latest revision as of 16:44, 8 September 2023

कम्प्यूटेशनल सम्मिश्रता सिद्धांत में, सम्मिश्रता वर्ग 2-एक्सप्टिटाइम (कभी-कभी 2-ईएक्सपी भी कहा जाता है) बड़े O(22p(n)) समय नोटेशन में एक नियतात्मक ट्यूरिंग मशीन द्वारा हल करने योग्य सभी निर्णय समस्याओं का सम्मुच्चय (गणित) है, जहां p(n) n का एक बहुपद फलन है।

डीटाइम के ​​संदर्भ में,

हम जानते हैं

P (सम्मिश्रता) ⊆ NP (सम्मिश्रता) ⊆ पीएसपीएसीई ⊆ एक्सप्टिटाइम ⊆ Nएक्सप्टिटाइम ⊆ एक्सप्टिटाइम ⊆ 2-एक्सप्टिटाइम ⊆ प्राथमिक है।

2-एक्सप्टिटाइम को स्पेस क्लास एईएक्सपीएसपीएसीई के रूप में भी दोबारा तैयार किया जा सकता है, ये समस्याएं एक्सपोनेंशियल स्पेस में एक वैकल्पिक ट्यूरिंग मशीन द्वारा हल की जा सकती हैं। यह देखने का एक तरीका है कि ईएक्सपीएसपीएसीई ⊆ 2-एक्सप्टिटाइम, क्योंकि एक वैकल्पिक ट्यूरिंग मशीन कम से कम एक नियतात्मक ट्यूरिंग मशीन जितनी शक्तिशाली होती है। [1]

2-एक्सप्टिटाइम सम्मिश्रता वर्गों के पदानुक्रम में एक वर्ग है जिसकी समय सीमा लगातार बढ़ती जा रही है। कक्षा 3-एक्सप्टिटाइम को 2-एक्सप्टिटाइम के ​​समान ही परिभाषित किया गया है, लेकिन तीन गुना घातीय समय सीमा के साथ है। इसे उच्चतर और उच्च समय सीमा के लिए सामान्यीकृत किया जा सकता है।

उदाहरण

कलन विधि के उदाहरण जिनमें कम से कम 2-एक्सप्टिटाइम की आवश्यकता होती है उनमें निम्न सम्मिलित हैं:

  • प्रेस्बर्गर अंकगणित के लिए प्रत्येक निर्णय प्रक्रिया के लिए कम से कम दोगुना घातीय समय की आवश्यकता होती है [2]
  • किसी क्षेत्र पर ग्रोबनेर आधार की गणना करना। सबसे खराब स्थिति में, ग्रोबनेर आधार में कई तत्व हो सकते हैं जो चर की संख्या में दोगुना घातीय है। दूसरी ओर, ग्रोबनेर आधार कलन विधि की सबसे खराब स्थिति की सम्मिश्रता चर की संख्या के साथ-साथ प्रवेश आकार में दोगुनी घातीय है। [3]
  • साहचर्य-कम्यूटेटिव एकीकरणकर्ताओं का एक पूरा सम्मुच्चय ढूँढना है [4]
  • संतोषजनक संगणना वृक्ष तर्क+ है (जो वास्तव में, 2-एक्सप्टिटाइम-पूर्ण है) [5]
  • वास्तविक बंद क्षेत्रों पर क्वांटिफायर उन्मूलन में दोगुना घातीय समय लगता है (बेलनाकार बीजगणितीय अपघटन देखें)।
  • नियमित अभिव्यक्ति के पूरक (सम्मुच्चय सिद्धांत) की गणना करना है [6]


2-एक्सप्टिटाइम-पूर्ण समस्याएँ

कई पूर्णतः अवलोकनीय खेलों के सामान्यीकरण एक्सप्टिटाइम-पूर्ण हैं। इन खेलों को स्तिथि चर और कार्यों/घटनाओं के एक सम्मुच्चय के संदर्भ में परिभाषित संक्रमण प्रणालियों के एक वर्ग के विशेष उदाहरणों के रूप में देखा जा सकता है जो स्तिथि चर के मूल्यों को बदलते हैं, साथ ही इस सवाल के साथ कि क्या जीतने की रणनीति उपस्थित है। पूरी तरह से अवलोकन योग्य समस्याओं के इस वर्ग का आंशिक रूप से अवलोकन योग्य प्रणालियों में सामान्यीकरण, सम्मिश्रता को एक्सप्टिटाइम-पूर्ण से 2-एक्सप्टिटाइम-पूर्ण तक बढ़ा देता है। [7]


यह भी देखें

संदर्भ

  1. ↑ Christos Papadimitriou, Computational Complexity (1994), ISBN 978-0-201-53082-7. Section 20.1, corollary 3, page 495.
  2. ↑ 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
  3. ↑ 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.
  4. ↑ 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.
  5. ↑ 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.
  6. ↑ 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.
  7. ↑ Jussi Rintanen (2004). "आंशिक अवलोकन के साथ योजना की जटिलता" (PDF). Proceedings of International Conference on Automated Planning and Scheduling. AAAI Press: 345–354.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=2-एक्सप्टिटाइम&oldid=256151’