डीटाइम

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

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

DTIME में जटिलता कक्षाएं

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

DTIME समय पदानुक्रम प्रमेय को संतुष्ट करता है, जिसका अर्थ है कि समय की बड़ी मात्रा में स्पर्शोन्मुख विश्लेषण हमेशा समस्याओं के बड़े सेट पैदा करता है।

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

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

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

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

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

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

मशीन मॉडल

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

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

सामान्यीकरण

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

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

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

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

अलविदा संतान. यदि हम एक विकल्प (जटिलता) का उपयोग करते हैं, तो हमारे पास ATIME संसाधन है।

संदर्भ

• 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.