डीटाइम

कम्प्यूटेशनल जटिलता सिद्धांत में, डीटाइम (या टाइम) नियतात्मक ट्यूरिंग मशीन के लिए गणना समय का कम्प्यूटेशनल संसाधन है। यह उस समय की मात्रा (या गणना चरणों की संख्या) को दर्शाता है जो सामान्य भौतिक कंप्यूटर निश्चित कलन विधि का उपयोग करके निश्चित कम्प्यूटेशनल समस्या का समाधान करता है। यह सबसे उत्तम रूप से अध्ययन किए गए जटिलता संसाधनों में से है, क्योंकि यह महत्वपूर्ण वास्तविक विश्व के संसाधन (किसी समस्या का समाधान करने में कंप्यूटर को लगने वाला समय) से अधिक निकटता से युग्मित होता है।

संसाधन डीटाइम का उपयोग जटिलता वर्गों, सभी निर्णय समस्याओं के सेट को परिभाषित करने के लिए किया जाता है जिन्हें निश्चित मात्रा में गणना के समय का उपयोग करके समाधान किया जा सकता है। यदि इनपुट आकार n के समस्या का समाधान $O(f(n))$ से किया जा सकता है, तो निकट जटिलता ${\mathsf {DTIME}}(f(n))$ (या ${\mathsf {TIME}}(f(n))$) वर्ग है, उपयोग किए गए मेमोरी स्पेस (कम्प्यूटेशनल संसाधन) की मात्रा पर कोई प्रतिबंध नहीं है, किंतु कुछ अन्य जटिल संसाधनों (जैसे अल्टरनेशन (जटिलता)) पर प्रतिबंध हो सकता है।

डीटाइम में जटिलता कक्षाएं

कई महत्वपूर्ण जटिलता वर्गों को डीटाइम के ​​​​संदर्भ में परिभाषित किया गया है, जिसमें वे सभी समस्याएं सम्मिलित हैं जिन्हें निश्चित समय में समाधान किया जा सकता है। किसी जटिलता वर्ग को परिभाषित करने के लिए किसी भी उचित जटिलता फ़ंक्शन का उपयोग किया जा सकता है, किंतु केवल कुछ वर्ग ही अध्ययन के लिए उपयोगी होते हैं। सामान्यतः, हम चाहते हैं कि हमारी जटिल कक्षाएं कम्प्यूटेशनल मॉडल में परिवर्तन के प्रतिकूल स्थिर हों, और सबरूटीन्स की संरचना के अंतर्गत बंद हो जाएं।डीटाइम समय पदानुक्रम प्रमेय को संतुष्ट करता है, जिसका अर्थ है कि असम्बद्ध रूप से बड़ी मात्रा में समय स्पर्शोन्मुख विश्लेषण सदैव समस्याओं के बड़े सेट उत्पन्न करता है।

प्रसिद्ध जटिलता वर्ग P (जटिलता) में वे सभी समस्याएं सम्मिलित हैं जिन्हें डीटाइम की बहुपद मात्रा में समाधान किया जा सकता है। इसे औपचारिक रूप से इस प्रकार परिभाषित किया जा सकता है:

${\mathsf {P}}=\bigcup _{k\in \mathbb {N} }{\mathsf {DTIME}}(n^{k})$

P सबसे छोटा स्थिर वर्ग है जिसमें रैखिक-समय ${\mathsf {DTIME}}\left(n\right)$ की समस्याएं सम्मिलित हैं (एएमएस 2004, व्याख्यान 2.2, पृष्ठ 20)। P कम्प्यूटेशनल रूप से व्यवहार्य माने जाने वाले सबसे बड़े जटिलता वर्गों में से है।

नियतिवादी समय का उपयोग करने वाला अधिक बड़ा वर्ग ईएक्सपी टाइम है, जिसमें घातांकीय समय में नियतिवादी मशीन का उपयोग करके समाधान की जाने वाली सभी समस्याएं सम्मिलित हैं। औपचारिक रूप से, निकट है:

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

बड़े जटिलता वर्गों को इसी प्रकार परिभाषित किया जा सकता है। समय पदानुक्रम प्रमेय के कारण, ये वर्ग जटिल पदानुक्रम बनाते हैं; हम जानते हैं कि ${\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}$, इससे ऊपर है।

मशीन मॉडल

डीटाइम को परिभाषित करने के लिए उपयोग किया जाने वाला त्रुटिहीन मशीन मॉडल संसाधन की शक्ति को प्रभावित किए बिना भिन्न हो सकता है। साहित्य में परिणाम प्रायः मल्टीटेप ट्यूरिंग मशीनों का उपयोग करते हैं, प्रायः जब अधिक छोटी समय की कक्षाओं पर वर्णन करते हैं। विशेष रूप से, मल्टीटेप नियतात्मक ट्यूरिंग मशीन कभी भी सिंगलटेप मशीन की तुलना में द्विघात समय स्पीडअप से अधिक प्रदान नहीं कर सकती है।

उपयोग किए गए समय की मात्रा में गुणक स्थिरांक डीटाइम कक्षाओं की शक्ति को नहीं परिवर्तित करते हैं; परिमित अवस्था नियंत्रण में अवस्थाओं की संख्या बढ़ाकर निरंतर गुणात्मक गति सदैव प्राप्त की जा सकती है। पापादिमित्रीउ के कथन में, L भाषा के लिए ,

$L\in {\mathsf {DTIME}}(f(n))$ फिर, किसी के लिए $\epsilon >0$, $L\in {\mathsf {DTIME}}(f'(n))$ जहाँ $f'(n)=\epsilon f(n)+n+2$

सामान्यीकरण

नियतात्मक ट्यूरिंग मशीन के अतिरिक्त किसी अन्य मॉडल का उपयोग करते हुए, डीटाइम के ​​विभिन्न सामान्यीकरण और प्रतिबंध हैं। उदाहरण के लिए, यदि गैर-नियतात्मक ट्यूरिंग मशीन का उपयोग करते हैं, तो हमारे निकट एन टाइम संसाधन है। डीटाइम की अभिव्यंजक शक्तियों और अन्य कम्प्यूटेशनल संसाधनों के मध्य संबंध को अधिक कम अध्ययन किया गया है। कुछ ज्ञात परिणामों में से है:

${\mathsf {DTIME}}(O(n))\neq {\mathsf {NTIME}}(O(n))$

मल्टीटेप मशीनों के लिए, इसे आगे बढ़ाया गया है:

${\mathsf {DTIME}}(O(n{\sqrt {\log ^{*}n}}))\neq {\mathsf {NTIME}}(O(n{\sqrt {\log ^{*}n}}))$

संथानम द्वारा,

यदि हम वैकल्पिक ट्यूरिंग मशीन का उपयोग करते हैं, तो हमारे निकट एटाइम संसाधन होता है।

संदर्भ

• American Mathematical Society (2004). Rudich, Steven and Avi Wigderson (ed.). Computational Complexity Theory. American Mathematical Society and Institute for Advanced Study. ISBN 0-8218-2872-X.
• Papadimitriou, Christos H. (1994). Computational Complexity. Reading, Massachusetts: Addison-Wesley. ISBN 0-201-53082-1.