2-एक्सप्टिटाइम

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

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

${\mathsf {2{\mbox{-}}EXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}\left(2^{2^{n^{k}}}\right).$

हम जानते हैं

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

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

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

उदाहरण

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

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

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

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

यह भी देखें

• दोहरा घातीय कार्य