डीटाइम - Revision history

Abhishekkshukla at 07:04, 4 September 2023

2023-09-04T07:04:17Z

← Older revision		Revision as of 12:34, 4 September 2023
Line 55:		Line 55:
	\| isbn = 0-201-53082-1		\| isbn = 0-201-53082-1
	}}		}}

	~~{{ComplexityClasses}}~~

	{{DEFAULTSORT:Dtime}}		{{DEFAULTSORT:Dtime}}

Manidh at 06:12, 11 July 2023

2023-07-11T06:12:58Z

← Older revision		Revision as of 11:42, 11 July 2023
Line 58:		Line 58:
	{{ComplexityClasses}}		{{ComplexityClasses}}

	{{DEFAULTSORT:Dtime}}~~[[Category: कम्प्यूटेशनल संसाधन]] [[Category: जटिलता वर्ग]]~~		{{DEFAULTSORT:Dtime}}

			[[Category:Collapse templates\|Dtime]]
			[[Category:Created On 27/06/2023\|Dtime]]
	[[Category: ~~Machine Translated Page~~]]		[[Category:Machine Translated Page\|Dtime]]
	[[Category:Created On 27/06/2023]]		[[Category:Navigational boxes\| ]]
	[[Category:Vigyan Ready]]		[[Category:Navigational boxes without horizontal lists\|Dtime]]
			[[Category:Pages with script errors\|Dtime]]
			[[Category:Sidebars with styles needing conversion\|Dtime]]
			[[Category:Template documentation pages\|Documentation/doc]]
			[[Category:Templates Vigyan Ready\|Dtime]]
			[[Category:Templates generating microformats\|Dtime]]
			[[Category:Templates that are not mobile friendly\|Dtime]]
			[[Category:Templates using TemplateData\|Dtime]]
			[[Category:Wikipedia metatemplates\|Dtime]]
			[[Category:कम्प्यूटेशनल संसाधन\|Dtime]]
			[[Category:जटिलता वर्ग\|Dtime]]

Indicwiki: 8 revisions imported from :alpha:डीटाइम

2023-07-10T12:58:20Z

8 revisions imported from alpha:डीटाइम

← Older revision	Revision as of 18:28, 10 July 2023
(No difference)

alpha>Neeraja: added Category:Vigyan Ready using HotCat

2023-07-10T05:53:16Z

added Category:Vigyan Ready using HotCat

← Older revision		Revision as of 11:23, 10 July 2023
Line 64:		Line 64:
	[[Category: Machine Translated Page]]		[[Category: Machine Translated Page]]
	[[Category:Created On 27/06/2023]]		[[Category:Created On 27/06/2023]]
			[[Category:Vigyan Ready]]

alpha>Shivam at 19:38, 5 July 2023

2023-07-05T19:38:09Z

← Older revision		Revision as of 01:08, 6 July 2023
Line 5:		Line 5:
	== डीटाइम में जटिलता कक्षाएं ==		== डीटाइम में जटिलता कक्षाएं ==

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

	प्रसिद्ध जटिलता वर्ग [[पी (जटिलता)\|P (जटिलता)]] में वे सभी समस्याएं सम्मिलित हैं जिन्हें डीटाइम की बहुपद मात्रा में समाधान किया जा सकता है। इसे औपचारिक रूप से इस प्रकार परिभाषित किया जा सकता है:		प्रसिद्ध जटिलता वर्ग [[पी (जटिलता)\|P (जटिलता)]] में वे सभी समस्याएं सम्मिलित हैं जिन्हें डीटाइम की बहुपद मात्रा में समाधान किया जा सकता है। इसे औपचारिक रूप से इस प्रकार परिभाषित किया जा सकता है:
Line 13:		Line 12:
	P सबसे छोटा स्थिर वर्ग है जिसमें रैखिक-समय <math>\mathsf{DTIME}\left(n\right)</math> की समस्याएं सम्मिलित हैं (एएमएस 2004, व्याख्यान 2.2, पृष्ठ 20)। P कम्प्यूटेशनल रूप से व्यवहार्य माने जाने वाले सबसे बड़े जटिलता वर्गों में से है।		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{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>, इससे ऊपर है।

alpha>Shivam at 19:37, 5 July 2023

2023-07-05T19:37:08Z

← Older revision		Revision as of 01:07, 6 July 2023
Line 4:		Line 4:

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

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

alpha>Shivam at 10:47, 5 July 2023

2023-07-05T10:47:27Z

← Older revision		Revision as of 16:17, 5 July 2023
Line 1:		Line 1:
	[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''डीटाइम''' (या टाइम) [[नियतात्मक ट्यूरिंग मशीन]] के लिए [[गणना समय]] का [[कम्प्यूटेशनल संसाधन]] है। यह उस समय की मात्रा (या गणना चरणों की संख्या) को दर्शाता है जो सामान्य भौतिक कंप्यूटर निश्चित [[कलन विधि]] का उपयोग करके निश्चित [[कम्प्यूटेशनल समस्या]] का समाधान करता है। यह सबसे उत्तम रूप से अध्ययन किए गए जटिलता संसाधनों में से है, क्योंकि यह महत्वपूर्ण वास्तविक विश्व के संसाधन (किसी समस्या का समाधान करने में कंप्यूटर को लगने वाला समय) से अधिक निकटता से युग्मित होता है।		[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, '''डीटाइम''' (या टाइम) [[नियतात्मक ट्यूरिंग मशीन]] के लिए [[गणना समय]] का [[कम्प्यूटेशनल संसाधन]] है। यह उस समय की मात्रा (या गणना चरणों की संख्या) को दर्शाता है जो सामान्य भौतिक कंप्यूटर निश्चित [[कलन विधि]] का उपयोग करके निश्चित [[कम्प्यूटेशनल समस्या]] का समाधान करता है। यह सबसे उत्तम रूप से अध्ययन किए गए जटिलता संसाधनों में से है, क्योंकि यह महत्वपूर्ण वास्तविक विश्व के संसाधन (किसी समस्या का समाधान करने में कंप्यूटर को लगने वाला समय) से अधिक निकटता से युग्मित होता है।

	संसाधन डीटाइम का उपयोग [[जटिलता वर्ग\|जटिलता वर्गों]], सभी [[निर्णय समस्या\|निर्णय समस्याओं]] के सेट को परिभाषित करने के लिए किया जाता है जिन्हें निश्चित मात्रा में गणना समय का उपयोग करके समाधान किया जा सकता है। यदि इनपुट आकार ''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))}}) वर्ग है, उपयोग किए गए [[मेमोरी स्पेस (कम्प्यूटेशनल संसाधन)]] की मात्रा पर कोई प्रतिबंध नहीं है, किंतु कुछ अन्य जटिल संसाधनों (जैसे अल्टरनेशन (जटिलता)) पर प्रतिबंध हो सकता है।

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

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

alpha>Shivam at 12:41, 3 July 2023

2023-07-03T12:41:35Z

← Older revision		Revision as of 18:11, 3 July 2023
Line 6:		Line 6:
	कई महत्वपूर्ण जटिलता वर्गों को डीटाइम के संदर्भ में परिभाषित किया गया है, जिसमें वे सभी समस्याएं सम्मिलित हैं जिन्हें निश्चित समय में समाधान किया जा सकता है। किसी जटिलता वर्ग को परिभाषित करने के लिए किसी भी उचित जटिलता फ़ंक्शन का उपयोग किया जा सकता है, किंतु केवल कुछ वर्ग ही अध्ययन के लिए उपयोगी होते हैं। सामान्यतः, हम चाहते हैं कि हमारी जटिलता कक्षाएं कम्प्यूटेशनल मॉडल में परिवर्तन के प्रतिकूल स्थिर हों, और सबरूटीन्स की संरचना के अंतर्गत बंद हो जाएं।		कई महत्वपूर्ण जटिलता वर्गों को डीटाइम के संदर्भ में परिभाषित किया गया है, जिसमें वे सभी समस्याएं सम्मिलित हैं जिन्हें निश्चित समय में समाधान किया जा सकता है। किसी जटिलता वर्ग को परिभाषित करने के लिए किसी भी उचित जटिलता फ़ंक्शन का उपयोग किया जा सकता है, किंतु केवल कुछ वर्ग ही अध्ययन के लिए उपयोगी होते हैं। सामान्यतः, हम चाहते हैं कि हमारी जटिलता कक्षाएं कम्प्यूटेशनल मॉडल में परिवर्तन के प्रतिकूल स्थिर हों, और सबरूटीन्स की संरचना के अंतर्गत बंद हो जाएं।

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

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

	नियतात्मक ट्यूरिंग मशीन के अतिरिक्त किसी अन्य मॉडल का उपयोग करते हुए, डीटाइम के विभिन्न सामान्यीकरण और प्रतिबंध हैं। उदाहरण के लिए, यदि [[गैर-नियतात्मक ट्यूरिंग मशीन]] का उपयोग करते हैं, तो हमारे निकट एन[[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> है:		नियतात्मक ट्यूरिंग मशीन के अतिरिक्त किसी अन्य मॉडल का उपयोग करते हुए, डीटाइम के विभिन्न सामान्यीकरण और प्रतिबंध हैं। उदाहरण के लिए, यदि [[गैर-नियतात्मक ट्यूरिंग मशीन]] का उपयोग करते हैं, तो हमारे निकट एन [[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)) \neq \mathsf{NTIME}(O(n))</math>
	मल्टीटेप मशीनों के लिए, इसे आगे बढ़ाया गया है:		मल्टीटेप मशीनों के लिए, इसे आगे बढ़ाया गया है:

alpha>Shivam at 12:36, 3 July 2023

2023-07-03T12:36:06Z

Show changes

alpha>Mithlesh at 12:09, 3 July 2023

2023-07-03T12:09:20Z

← Older revision		Revision as of 11:42, 11 July 2023
Line 58:		Line 58:
	{{ComplexityClasses}}		{{ComplexityClasses}}

	{{DEFAULTSORT:Dtime}}~~[[Category: कम्प्यूटेशनल संसाधन]] [[Category: जटिलता वर्ग]]~~		{{DEFAULTSORT:Dtime}}

			[[Category:Collapse templates\|Dtime]]
			[[Category:Created On 27/06/2023\|Dtime]]
	[[Category: ~~Machine Translated Page~~]]		[[Category:Machine Translated Page\|Dtime]]
	[[Category:Created On 27/06/2023]]		[[Category:Navigational boxes\| ]]
	[[Category:Vigyan Ready]]		[[Category:Navigational boxes without horizontal lists\|Dtime]]
			[[Category:Pages with script errors\|Dtime]]
			[[Category:Sidebars with styles needing conversion\|Dtime]]
			[[Category:Template documentation pages\|Documentation/doc]]
			[[Category:Templates Vigyan Ready\|Dtime]]
			[[Category:Templates generating microformats\|Dtime]]
			[[Category:Templates that are not mobile friendly\|Dtime]]
			[[Category:Templates using TemplateData\|Dtime]]
			[[Category:Wikipedia metatemplates\|Dtime]]
			[[Category:कम्प्यूटेशनल संसाधन\|Dtime]]
			[[Category:जटिलता वर्ग\|Dtime]]

← Older revision		Revision as of 17:39, 3 July 2023
Line 1:		Line 1:
	[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, DTIME (या TIME) एक [[नियतात्मक ट्यूरिंग मशीन]] के लिए [[गणना समय]] का [[कम्प्यूटेशनल संसाधन]] है। यह उस समय की मात्रा (या गणना चरणों की संख्या) को दर्शाता है जो एक सामान्य भौतिक कंप्यूटर एक निश्चित [[कलन विधि]] का उपयोग करके एक निश्चित [[कम्प्यूटेशनल समस्या]] को हल करने में लेगा। यह सबसे अच्छी तरह से अध्ययन किए गए जटिलता संसाधनों में से एक है, क्योंकि यह एक महत्वपूर्ण वास्तविक दुनिया के संसाधन (किसी समस्या को हल करने में कंप्यूटर को लगने वाला समय) से बहुत निकटता से मेल खाता है।		[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, DTIME (या TIME) [[नियतात्मक ट्यूरिंग मशीन]] के लिए [[गणना समय]] का [[कम्प्यूटेशनल संसाधन]] है। यह उस समय की मात्रा (या गणना चरणों की संख्या) को दर्शाता है जो सामान्य भौतिक कंप्यूटर निश्चित [[कलन विधि]] का उपयोग करके निश्चित [[कम्प्यूटेशनल समस्या]] को हल करने में लेगा। यह सबसे अच्छी तरह से अध्ययन किए गए जटिलता संसाधनों में से है, क्योंकि यह महत्वपूर्ण वास्तविक दुनिया के संसाधन (किसी समस्या को हल करने में कंप्यूटर को लगने वाला समय) से बहुत निकटता से मेल खाता है।

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

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

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

	:<math>\mathsf{P} = \bigcup_{k\in\mathbb{N}} \mathsf{DTIME}(n^k)</math>		:<math>\mathsf{P} = \bigcup_{k\in\mathbb{N}} \mathsf{DTIME}(n^k)</math>
	पी सबसे छोटा मजबूत वर्ग है जिसमें रैखिक-समय की समस्याएं शामिल हैं <math>\mathsf{DTIME}\left(n\right)</math> (एएमएस 2004, व्याख्यान 2.2, पृष्ठ 20)। पी कम्प्यूटेशनल रूप से व्यवहार्य माने जाने वाले सबसे बड़े जटिलता वर्गों में से एक है।		पी सबसे छोटा मजबूत वर्ग है जिसमें रैखिक-समय की समस्याएं शामिल हैं <math>\mathsf{DTIME}\left(n\right)</math> (एएमएस 2004, व्याख्यान 2.2, पृष्ठ 20)। पी कम्प्यूटेशनल रूप से व्यवहार्य माने जाने वाले सबसे बड़े जटिलता वर्गों में से है।

	नियतिवादी समय का उपयोग करने वाला एक बहुत बड़ा वर्ग [[EXPTIME]] है, जिसमें घातांकीय समय में नियतिवादी मशीन का उपयोग करके हल की जाने वाली सभी समस्याएं शामिल हैं। औपचारिक रूप से, हमारे पास है		नियतिवादी समय का उपयोग करने वाला बहुत बड़ा वर्ग [[EXPTIME]] है, जिसमें घातांकीय समय में नियतिवादी मशीन का उपयोग करके हल की जाने वाली सभी समस्याएं शामिल हैं। औपचारिक रूप से, हमारे पास है
	:<math> \mathsf{EXPTIME} = \bigcup_{k \in \mathbb{N} } \mathsf{DTIME} \left( 2^{ n^k } \right) . </math>		:<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>		DTIME को परिभाषित करने के लिए उपयोग किया जाने वाला सटीक मशीन मॉडल संसाधन की शक्ति को प्रभावित किए बिना भिन्न हो सकता है। साहित्य में परिणाम अक्सर [[मल्टीटेप ट्यूरिंग मशीन]]ों का उपयोग करते हैं, खासकर जब बहुत छोटी समय की कक्षाओं पर चर्चा करते हैं। विशेष रूप से, मल्टीटेप नियतात्मक ट्यूरिंग मशीन कभी भी सिंगलटेप मशीन की तुलना में द्विघात समय स्पीडअप से अधिक प्रदान नहीं कर सकती है।<ref>Papadimitriou 1994, Thrm. 2.1</ref>
	उपयोग किए गए समय की मात्रा में गुणक स्थिरांक DTIME कक्षाओं की शक्ति को नहीं बदलते हैं; परिमित राज्य नियंत्रण में राज्यों की संख्या बढ़ाकर एक निरंतर गुणात्मक गति हमेशा प्राप्त की जा सकती है। पापादिमित्रीउ के बयान में,<ref>1994, Thrm. 2.2</ref> एक भाषा के लिए {{mvar\|L}},		उपयोग किए गए समय की मात्रा में गुणक स्थिरांक 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>.		:होने देना <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>.
Line 26:		Line 26:
	==सामान्यीकरण==		==सामान्यीकरण==

	नियतात्मक ट्यूरिंग मशीन के अलावा किसी अन्य मॉडल का उपयोग करते हुए, 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> है		नियतात्मक ट्यूरिंग मशीन के अलावा किसी अन्य मॉडल का उपयोग करते हुए, 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> है
	:<math>\mathsf{DTIME}(O(n)) \neq \mathsf{NTIME}(O(n))</math>		:<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>		:<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 संसाधन है।		यदि हम विकल्प (जटिलता) का उपयोग करते हैं, तो हमारे पास ATIME संसाधन है।

	==संदर्भ==		==संदर्भ==