डीटाइम: Difference between revisions

Revision as of 18:06, 3 July 2023

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

संसाधन डीटाइम का उपयोग जटिलता वर्गों, सभी निर्णय समस्याओं के सेट को परिभाषित करने के लिए किया जाता है जिन्हें निश्चित मात्रा में गणना समय का उपयोग करके समाधान किया जा सकता है। यदि इनपुट आकार 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}}$ , इससे ऊपर है।

मशीन मॉडल

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

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

L\in {\mathsf {DTIME}}(f(n))

फिर, किसी के लिए

\epsilon >0

,

L\in {\mathsf {DTIME}}(f'(n))

जहाँ

f'(n)=\epsilon f(n)+n+2

सामान्यीकरण

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

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

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

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

संथानम द्वारा,^[4]

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

संदर्भ

↑ Papadimitriou 1994, Thrm. 2.1
↑ 1994, Thrm. 2.2
↑ Paul Wolfgang, Nick Pippenger, Endre Szemerédi, William Trotter. On determinism versus non-determinism and related problems. 24th Annual Symposium on Foundations of Computer Science, 1983. doi:10.1109/SFCS.1983.39
↑ Rahul Santhanam, On separators, segregators and time versus space, 16th Annual IEEE Conference on Computational Complexity, 2001.

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.

[1] Papadimitriou 1994, Thrm. 2.1

[2] 1994, Thrm. 2.2

[3] Paul Wolfgang, Nick Pippenger, Endre Szemerédi, William Trotter. On determinism versus non-determinism and related problems. 24th Annual Symposium on Foundations of Computer Science, 1983. doi:10.1109/SFCS.1983.39

[4] Rahul Santhanam, On separators, segregators and time versus space, 16th Annual IEEE Conference on Computational Complexity, 2001.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, DTIME (या TIME) [[नियतात्मक ट्यूरिंग मशीन]] के लिए [[गणना समय]] का [[कम्प्यूटेशनल संसाधन]] है। यह उस समय की मात्रा (या गणना चरणों की संख्या) को दर्शाता है जो सामान्य भौतिक कंप्यूटर निश्चित [[कलन विधि]] का उपयोग करके निश्चित [[कम्प्यूटेशनल समस्या]] को हल करने में लेगा। यह सबसे अच्छी तरह से अध्ययन किए गए जटिलता संसाधनों में से है, क्योंकि यह महत्वपूर्ण वास्तविक दुनिया के संसाधन (किसी समस्या को हल करने में कंप्यूटर को लगने वाला समय) से बहुत निकटता से मेल खाता है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''डीटाइम''' (या टाइम) [[नियतात्मक ट्यूरिंग मशीन]] के लिए [[गणना समय]] का [[कम्प्यूटेशनल संसाधन]] है। यह उस समय की मात्रा (या गणना चरणों की संख्या) को दर्शाता है जो सामान्य भौतिक कंप्यूटर निश्चित [[कलन विधि]] का उपयोग करके निश्चित [[कम्प्यूटेशनल समस्या]] का समाधान करता है। यह सबसे उत्तम रूप से अध्ययन किए गए जटिलता संसाधनों में से है, क्योंकि यह महत्वपूर्ण वास्तविक विश्व के संसाधन (किसी समस्या का समाधान करने में कंप्यूटर को लगने वाला समय) से अधिक निकटता से युग्मित होता है।
-संसाधन DTIME का उपयोग [[जटिलता वर्ग]]ों, सभी [[निर्णय समस्या]]ओं के सेट को परिभाषित करने के लिए किया जाता है जिन्हें निश्चित मात्रा में गणना समय का उपयोग करके हल किया जा सकता है। यदि इनपुट आकार ''n'' की समस्या को हल किया जा सकता है {{tmath|O(f(n))}}, हमारे पास जटिलता वर्ग है {{tmath|\mathsf{DTIME}(f(n))}} (या {{tmath|\mathsf{TIME}(f(n))}}). उपयोग किए गए [[मेमोरी स्पेस (कम्प्यूटेशनल संसाधन)]] की मात्रा पर कोई प्रतिबंध नहीं है, लेकिन कुछ अन्य जटिलता संसाधनों (जैसे अल्टरनेशन (जटिलता)) पर प्रतिबंध हो सकता है।
+संसाधन डीटाइम का उपयोग [[जटिलता वर्ग|जटिलता वर्गों]], सभी [[निर्णय समस्या|निर्णय समस्याओं]] के सेट को परिभाषित करने के लिए किया जाता है जिन्हें निश्चित मात्रा में गणना समय का उपयोग करके समाधान किया जा सकता है। यदि इनपुट आकार ''n'' की समस्या का समाधान {{tmath|O(f(n))}} से किया जा सकता है, हमारे निकट जटिलता {{tmath|\mathsf{DTIME}(f(n))}} (या {{tmath|\mathsf{TIME}(f(n))}}) वर्ग है, उपयोग किए गए [[मेमोरी स्पेस (कम्प्यूटेशनल संसाधन)]] की मात्रा पर कोई प्रतिबंध नहीं है, किंतु कुछ अन्य जटिल संसाधनों (जैसे अल्टरनेशन (जटिलता)) पर प्रतिबंध हो सकता है।
-== DTIME में जटिलता कक्षाएं ==
+== डीटाइम में जटिलता कक्षाएं ==
-कई महत्वपूर्ण जटिलता वर्गों को DTIME के संदर्भ में परिभाषित किया गया है, जिसमें वे सभी समस्याएं शामिल हैं जिन्हें निश्चित समय में हल किया जा सकता है। किसी जटिलता वर्ग को परिभाषित करने के लिए किसी भी उचित जटिलता फ़ंक्शन का उपयोग किया जा सकता है, लेकिन केवल कुछ वर्ग ही अध्ययन के लिए उपयोगी होते हैं। सामान्य तौर पर, हम चाहते हैं कि हमारी जटिलता कक्षाएं कम्प्यूटेशनल मॉडल में बदलावों के खिलाफ मजबूत हों, और सबरूटीन्स की संरचना के तहत बंद हो जाएं।
+कई महत्वपूर्ण जटिलता वर्गों को डीटाइम के संदर्भ में परिभाषित किया गया है, जिसमें वे सभी समस्याएं सम्मिलित हैं जिन्हें निश्चित समय में समाधान किया जा सकता है। किसी जटिलता वर्ग को परिभाषित करने के लिए किसी भी उचित जटिलता फ़ंक्शन का उपयोग किया जा सकता है, किंतु केवल कुछ वर्ग ही अध्ययन के लिए उपयोगी होते हैं। सामान्यतः, हम चाहते हैं कि हमारी जटिलता कक्षाएं कम्प्यूटेशनल मॉडल में परिवर्तन के प्रतिकूल स्थिर हों, और सबरूटीन्स की संरचना के अंतर्गत बंद हो जाएं।
-DTIME [[समय पदानुक्रम प्रमेय]] को संतुष्ट करता है, जिसका अर्थ है कि समय की बड़ी मात्रा में [[स्पर्शोन्मुख विश्लेषण]] हमेशा समस्याओं के बड़े सेट पैदा करता है।
+डीटाइम [[समय पदानुक्रम प्रमेय]] को संतुष्ट करता है, जिसका अर्थ है कि असम्बद्ध रूप से बड़ी मात्रा में समय [[स्पर्शोन्मुख विश्लेषण]] सदैव समस्याओं के बड़े सेट उत्पन्न करता है। है।
-प्रसिद्ध जटिलता वर्ग [[पी (जटिलता)]] में वे सभी समस्याएं शामिल हैं जिन्हें DTIME की बहुपद मात्रा में हल किया जा सकता है। इसे औपचारिक रूप से इस प्रकार परिभाषित किया जा सकता है:
+प्रसिद्ध जटिलता वर्ग [[पी (जटिलता)|P (जटिलता)]] में वे सभी समस्याएं सम्मिलित हैं जिन्हें डीटाइम की बहुपद मात्रा में समाधान किया जा सकता है। इसे औपचारिक रूप से इस प्रकार परिभाषित किया जा सकता है:
 :<math>\mathsf{P} = \bigcup_{k\in\mathbb{N}} \mathsf{DTIME}(n^k)</math>
-पी सबसे छोटा मजबूत वर्ग है जिसमें रैखिक-समय की समस्याएं शामिल हैं <math>\mathsf{DTIME}\left(n\right)</math> (एएमएस 2004, व्याख्यान 2.2, पृष्ठ 20)। पी कम्प्यूटेशनल रूप से व्यवहार्य माने जाने वाले सबसे बड़े जटिलता वर्गों में से है।
+P सबसे छोटा स्थिर वर्ग है जिसमें रैखिक-समय <math>\mathsf{DTIME}\left(n\right)</math> की समस्याएं सम्मिलित हैं (एएमएस 2004, व्याख्यान 2.2, पृष्ठ 20)। P कम्प्यूटेशनल रूप से व्यवहार्य माने जाने वाले सबसे बड़े जटिलता वर्गों में से है।
-नियतिवादी समय का उपयोग करने वाला बहुत बड़ा वर्ग [[EXPTIME]] है, जिसमें घातांकीय समय में नियतिवादी मशीन का उपयोग करके हल की जाने वाली सभी समस्याएं शामिल हैं। औपचारिक रूप से, हमारे पास है
+नियतिवादी समय का उपयोग करने वाला अधिक बड़ा वर्ग [[EXPTIME|ईएक्सपी टाइम]] है, जिसमें घातांकीय समय में नियतिवादी मशीन का उपयोग करके समाधान की जाने वाली सभी समस्याएं सम्मिलित हैं। औपचारिक रूप से, हमारे निकट है:
 :<math> \mathsf{EXPTIME} = \bigcup_{k \in \mathbb{N} } \mathsf{DTIME} \left( 2^{ n^k } \right) . </math>
-बड़े जटिलता वर्गों को इसी तरह परिभाषित किया जा सकता है। समय पदानुक्रम प्रमेय के कारण, ये वर्ग सख्त पदानुक्रम बनाते हैं; हम वह जानते हैं <math>\mathsf{P} \subsetneq \mathsf{EXPTIME} </math>, और ऊपर।
+बड़े जटिलता वर्गों को इसी प्रकार परिभाषित किया जा सकता है। समय पदानुक्रम प्रमेय के कारण, ये वर्ग जटिल पदानुक्रम बनाते हैं; हम जानते हैं कि <math>\mathsf{P} \subsetneq \mathsf{EXPTIME} </math>, इससे ऊपर है।
 ==मशीन मॉडल==
-DTIME को परिभाषित करने के लिए उपयोग किया जाने वाला सटीक मशीन मॉडल संसाधन की शक्ति को प्रभावित किए बिना भिन्न हो सकता है। साहित्य में परिणाम अक्सर [[मल्टीटेप ट्यूरिंग मशीन]]ों का उपयोग करते हैं, खासकर जब बहुत छोटी समय की कक्षाओं पर चर्चा करते हैं। विशेष रूप से, मल्टीटेप नियतात्मक ट्यूरिंग मशीन कभी भी सिंगलटेप मशीन की तुलना में द्विघात समय स्पीडअप से अधिक प्रदान नहीं कर सकती है।<ref>Papadimitriou 1994, Thrm. 2.1</ref>
+डीटाइम को परिभाषित करने के लिए उपयोग किया जाने वाला त्रुटिहीन मशीन मॉडल संसाधन की शक्ति को प्रभावित किए बिना भिन्न हो सकता है। साहित्य में परिणाम प्रायः [[मल्टीटेप ट्यूरिंग मशीन|मल्टीटेप ट्यूरिंग मशीनों]] का उपयोग करते हैं, प्रायः जब अधिक छोटी समय की कक्षाओं पर वर्णन करते हैं। विशेष रूप से, मल्टीटेप नियतात्मक ट्यूरिंग मशीन कभी भी सिंगलटेप मशीन की तुलना में द्विघात समय स्पीडअप से अधिक प्रदान नहीं कर सकती है।<ref>Papadimitriou 1994, Thrm. 2.1</ref>
-उपयोग किए गए समय की मात्रा में गुणक स्थिरांक DTIME कक्षाओं की शक्ति को नहीं बदलते हैं; परिमित राज्य नियंत्रण में राज्यों की संख्या बढ़ाकर निरंतर गुणात्मक गति हमेशा प्राप्त की जा सकती है। पापादिमित्रीउ के बयान में,<ref>1994, Thrm. 2.2</ref> भाषा के लिए {{mvar|L}},
-:होने देना <math>L \in \mathsf{DTIME}(f(n))</math>. फिर, किसी के लिए <math>\epsilon > 0</math>, <math>L \in \mathsf{DTIME}(f'(n))</math>, कहाँ <math>f'(n) = \epsilon f(n) + n + 2</math>.
+उपयोग किए गए समय की मात्रा में गुणक स्थिरांक डीटाइम कक्षाओं की शक्ति को नहीं परिवर्तित करते हैं; परिमित अवस्था नियंत्रण में अवस्थाओं की संख्या बढ़ाकर निरंतर गुणात्मक गति सदैव प्राप्त की जा सकती है। पापादिमित्रीउ के कथन में,<ref>1994, Thrm. 2.2</ref> {{mvar|L}} भाषा के लिए ,
+:<math>L \in \mathsf{DTIME}(f(n))</math> फिर, किसी के लिए <math>\epsilon > 0</math>, <math>L \in \mathsf{DTIME}(f'(n))</math> जहाँ <math>f'(n) = \epsilon f(n) + n + 2</math>
 ==सामान्यीकरण==
-नियतात्मक ट्यूरिंग मशीन के अलावा किसी अन्य मॉडल का उपयोग करते हुए, DTIME के विभिन्न सामान्यीकरण और प्रतिबंध हैं। उदाहरण के लिए, यदि हम [[गैर-नियतात्मक ट्यूरिंग मशीन]] का उपयोग करते हैं, तो हमारे पास [[NTIME]] संसाधन है। DTIME की अभिव्यंजक शक्तियों और अन्य कम्प्यूटेशनल संसाधनों के बीच संबंध को बहुत कम समझा गया है। कुछ ज्ञात परिणामों में से एक<ref>Paul Wolfgang, [[Nick Pippenger]], [[Endre Szemerédi]], William Trotter. On determinism versus non-determinism and related problems. 24th Annual Symposium on Foundations of Computer Science, 1983. {{doi|10.1109/SFCS.1983.39}}</ref> है
+नियतात्मक ट्यूरिंग मशीन के अतिरिक्त किसी अन्य मॉडल का उपयोग करते हुए, डीटाइम के विभिन्न सामान्यीकरण और प्रतिबंध हैं। उदाहरण के लिए, यदि [[गैर-नियतात्मक ट्यूरिंग मशीन]] का उपयोग करते हैं, तो हमारे निकट एन[[NTIME|टाइम]] संसाधन है। डीटाइम की अभिव्यंजक शक्तियों और अन्य कम्प्यूटेशनल संसाधनों के मध्य संबंध को अधिक कम अध्ययन किया गया है। कुछ ज्ञात परिणामों में से <ref>Paul Wolfgang, [[Nick Pippenger]], [[Endre Szemerédi]], William Trotter. On determinism versus non-determinism and related problems. 24th Annual Symposium on Foundations of Computer Science, 1983. {{doi|10.1109/SFCS.1983.39}}</ref> है:
 :<math>\mathsf{DTIME}(O(n)) \neq \mathsf{NTIME}(O(n))</math>
-मल्टीटेप मशीनों के लिए. इसे आगे बढ़ाया गया
+मल्टीटेप मशीनों के लिए, इसे आगे बढ़ाया गया है:
 :<math>\mathsf{DTIME}(O(n\sqrt{\log^*n})) \neq \mathsf{NTIME}(O(n\sqrt{\log^*n}))</math>
-अलविदा संतान.<ref>Rahul Santhanam, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2392 On separators, segregators and time versus space], 16th Annual IEEE Conference on Computational Complexity, 2001.</ref>
+संथानम द्वारा,<ref>Rahul Santhanam, [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.22.2392 On separators, segregators and time versus space], 16th Annual IEEE Conference on Computational Complexity, 2001.</ref>
-यदि हम विकल्प (जटिलता) का उपयोग करते हैं, तो हमारे पास ATIME संसाधन है।
+यदि हम वैकल्पिक ट्यूरिंग मशीन का उपयोग करते हैं, तो हमारे निकट एटाइम संसाधन होता है।
 ==संदर्भ==

v t e Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Anonymous

Search

डीटाइम: Difference between revisions

Namespaces

More

Page actions

Revision as of 18:06, 3 July 2023

Contents

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

मशीन मॉडल

सामान्यीकरण

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

डीटाइम: Difference between revisions

Revision as of 18:06, 3 July 2023

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

मशीन मॉडल

सामान्यीकरण

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories