समय पदानुक्रम प्रमेय: Difference between revisions

Latest revision as of 09:53, 23 August 2023

अभिकलनात्मक सम्मिश्र सिद्धांत में, समय पदानुक्रम प्रमेय ट्यूरिंग मशीनों पर समयबद्ध संगणना के बारे में महत्वपूर्ण कथन हैं। और अनौपचारिक रूप से ये प्रमेय कहती है कि अधिक समय दिए जाने पर ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए ऐसी समस्याएं जिन्हें n² समय के साथ समाधान किया जा सकता है लेकिन n समय के साथ समाधान नहीं किया जा सकता है।

नियतात्मक मल्टीटेप ट्यूरिंग मशीन के लिए समय पदानुक्रम प्रमेय को पसमाधानी बार 1965 में रिचर्ड ई. स्टर्न्स और ज्यूरिस हार्टमैनिस द्वारा सिद्ध किया गया था।^[1] एक साल बाद इसमें सुधार किया गया जब एफ. सी. हेनी और रिचर्ड ई. स्टर्न्स ने यूनिवर्सल ट्यूरिंग मशीन की दक्षता में सुधार किया गया था।^[2] और इस प्रकार प्रमेय के परिणामस्वरूप प्रत्येक नियतात्मक समय-सीमाबद्ध सम्मिश्र वर्ग के लिए स्ट्रिक्टली से बड़ा सम्मिश्र वर्ग है और इसलिए सम्मिश्र वर्ग की समय-सीमाबद्ध में पदानुक्रम पूरी तरह से नष्ट नहीं होता है और इस प्रकार अधिक सटीक रूप से नियतात्मक ट्यूरिंग मशीन के लिए समय पदानुक्रम प्रमेय बताता है कि सभी रचनात्मक फलन के लिए समय कंस्ट्रक्टिबल फलन f(n) है।

{\mathsf {DTIME}}\left(o\left({\frac {f(n)}{\log f(n)}}\right)\right)\subsetneq {\mathsf {DTIME}}(f(n))

,

जहां DTIME (f(n)) समय O, (f(n)) में व्याख्या करने योग्य डिसिशन समस्याओं की सम्मिश्र वर्ग को दर्शाता है। ध्यान दें कि बाएं हाथ के वर्ग में बहुत कम O अंकन पद्धति के रूप में सम्मलित है, जो कि f(n) समय से कम समय में सोल्वेबल निर्णय समस्याओं के समुच्चय को संदर्भित करता है।

गैर-नियतात्मक ट्यूरिंग मशीन के लिए समय पदानुक्रम प्रमेय मूल रूप से 1972 में स्टीफन कुक द्वारा सिद्ध किया गया था।^[3] वर्ष 1978 में जोएल सेफेरस, माइकल जे. फिशर और अल्बर्ट आर. मेयर द्वारा एक सम्मिश्र प्रमाण के माध्यम से इसके वर्तमान स्वरूप में सुधार किया गया है।^[4] और इस प्रकार विशेष रूप में वर्ष 1983 में, स्टैनिस्लाव ज़ैक ने साधारण प्रमाण के साथ वही परिणाम प्राप्त किये थे।^[5] जो गैर-नियतात्मक ट्यूरिंग मशीन के लिए समय पदानुक्रम प्रमेय बताता है कि यदि g(n) समय कंस्ट्रक्टिबल फलन f(n+1) = o(g(n)) के रूप में है,

{\mathsf {NTIME}}(f(n))\subsetneq {\mathsf {NTIME}}(g(n))

.

किसी समष्टि के लिए एनालॉग प्रमेय समष्टि पदानुक्रम प्रमेय के रूप में होती हैं। इस प्रकार एक समान प्रमेय समयबद्ध प्रोबबिलिस्टिक सम्मिश्र वर्ग के लिए ज्ञात नहीं है, जब तक कि वर्ग के पास सम्मिश्र के रूप में एक भी बिट उपलब्ध न हो।^[6]

पृष्ठभूमि

दोनों प्रमेयों एक समय कंस्ट्रक्टिबल फलन की नोशन का उपयोग करते हैं। एक फलन (गणित) $f:\mathbb {N} \rightarrow \mathbb {N}$ समय-कंस्ट्रक्टिबल के रूप में है, यदि कोई नियतात्मक ट्यूरिंग मशीन के रूप में उपस्थित है जैसे कि प्रत्येक , $n\in \mathbb {N}$ , के रूप मेंहोते है, यदि मशीन को n वाले इनपुट के साथ शुरू किया जाता है, तो यह ठीक f(n) चरणों के बाद रुक जाती है और इस प्रकार गैर-ऋणात्मक पूर्णांक गुणांक वाले सभी बहुपद समय-कंस्ट्रक्टिबल के रूप में होते है, जैसे कि 2ⁿ जैसे घातीय फलन के रूप में होते है

प्रमाण अवलोकन

हमें यह सिद्ध करने की आवश्यकता है कि कुछ समय वर्ग TIME(g(n)) कुछ समय वर्ग TIME(f(n)) से पूर्णतः बड़ा होता है। हम एक ऐसी मशीन का निर्माण करके ऐसा करते हैं जो कैंटर के विकर्ण लॉजिक्स द्वारा TIME(f(n)) में नहीं हो सकती है। फिर हम सिमुलेशन मशीन का उपयोग करके दिखाते हैं कि मशीन TIME(g(n)) के रूप में होती है।

नियतात्मक समय पदानुक्रम प्रमेय

कथन

समय पदानुक्रम प्रमेय, यदि f(n) समय-कंस्ट्रक्टिबल फलन है, तो एक डिसिशन प्रॉब्लम के रूप में उपस्थित है जिसे सबसे खराब स्थिति वाले नियतात्मक समय f(n) में समाधान नहीं किया जा सकता है, लेकिन सबसे खराब स्थिति वाले नियतात्मक समय में इसे f(n)log f(n) से बड़े आकार में समाधान किया जा सकता है। उदाहरण इस प्रकार है,

{\mathsf {DTIME}}(f(n))\subsetneq {\mathsf {DTIME}}\left(f(n)\log ^{2}f(n)\right).

नोट 1. f(n) कम से कम n है, क्योंकि छोटे फलन कभी भी समय-कंस्ट्रक्टिबल नहीं होते हैं।

नोट 2. एल्गोरिदम का सटीक विवरण निम्न प्रकार से छोटे फलन का उपयोग करके लिखा जा सकता है, यदि f(n) समय-कंस्ट्रक्टिबल है, तो

{\mathsf {DTIME}}\left(o\left({\frac {f(n)}{\log f(n)}}\right)\right)\subsetneq {\mathsf {DTIME}}\left(f(n)\right).

उदाहरण के लिए, टाइम एनलॉग में सोल्वेबल समस्याएं nlog²n के रूप में होती है, लेकिन समय n अंदर है लेकिन समय n के रूप में नहीं होती है, यह ${\displaystyle f(n)=n\log n}$ समुच्चयिंग के बाद आता है चूंकि n ${\displaystyle o\left(n\log n\right).}$ के रूप में होता है,

प्रमाण

हम यहां एक विकर्स रिजल्ट्स का प्रूफ सम्मलित करते हैं, अर्थात् DTIME(f(n)), DTIME(f(2n + 1) का एक स्ट्रिक्ट्ली उपसमूह है, क्योंकि यह सरल है लेकिन प्रूफ विचार को दर्शाता है। प्रूफ को f(n)logf(n) तक कैसे बढ़ाया जाए, इसकी जानकारी के लिए इस अनुभाग के नीचे दिखाया जाता है।

इसे सिद्ध करने के लिए, हम पसमाधाने मशीन की एन्कोडिंग और उनके इनपुट की लैंग्वेज को परिभाषित करते हैं जो उन्हें f के भीतर रुकने का कारण बनता है

H_{f}=\left\{([M],x)\ |\ M\ {\text{accepts}}\ x\ {\text{in}}\ f(|x|)\ {\text{steps}}\right\}.

यहां ध्यान दें कि यह एक समय-वर्ग है। यह उन मशीन (M,x) के लिए मशीन और इनपुट के जोड़े का समुच्चय है जिससे कि मशीन M f(|x|) चरणों के भीतर स्वीकार करते है।

यहां, M एक नियतात्मक ट्यूरिंग मशीन है और x इसका इनपुट है और इसके टेप की प्रारंभिक सामग्री है। [M ] एक इनपुट को दर्शाता है, जो ट्यूरिंग मशीन M को एनकोड करता है। मान लीजिए कि M टुपल का आकार ([M], x) के रूप में है।

हम जानते हैं कि हम नियतात्मक ट्यूरिंग मशीन R के माध्यम से H_f की मेम्बरशिप तय कर सकते हैं और जो पसमाधाने f(|x|) की सं संगणना करके और फिर उस लंबाई की 0s की एक पंक्ति लिखकर और फिर इसका उपयोग करके f(x) चरणों के लिए M का अनुकरण करती है। और इस प्रकार अधिकतम इतने चरणों के लिए M का अनुकरण करने के लिए एक घड़ी या काउंटर के रूप में 0s की पंक्ति के रूप में अनुकरण करती है, प्रत्येक चरण में, अगली कार्रवाई क्या होगी, यह तय करने के लिए सिमुलेशन मशीन को M की परिभाषा को देखने की जरूरत है। यह कहना सुरक्षित है कि इसमें अधिकतम f(m)³ ऑपरेशन लगते हैं, क्योंकि यह ज्ञात है कि समय सम्मिश्र T(n) की मशीन का अनुकरण एक मल्टीटेप मशीन पर समय $O(T(n)\cdot |M|)$ में प्राप्त किया जा सकता है, जहाँ |M| M की एन्कोडिंग की लंबाई है हमारे पास है

H_{f}\in {\mathsf {TIME}}\left(f(m)^{3}\right).

शेष प्रूफ इस प्रकार दिखा देंते है

H_{f}\notin {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right)

जिससे कि यदि हम m के स्थान पर 2n + 1 प्रतिस्थापित करते है, तो हमें वांछित परिणाम प्राप्त होते है। आइए मान लें H_f की इस समय सम्मिश्र वर्ग है और हम एक अन्तर्विरोध पर पहुंच जाते है।

यदि H_f इस समय सम्मिश्र वर्ग में है, तो वहां एक मशीन K के रूप में उपस्थित है, जो कुछ मशीन विवरण [M] और इनपुट x दिए जाने पर यह तय करती है कि टुपल ([M], x) H_f के रूप में उपस्थित है

{\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right).

हम इस K का उपयोग एक अन्य मशीन N के निर्माण के लिए करते हैं, जो एक मशीन विवरण [M] के रूप में होती है और K को टुपल ([M], [M]) पर चलाती है, अर्थात M को K द्वारा अपने स्वयं के कोड पर सिम्युलेटेड किया जाता है और यदि K अस्वीकार करता है तो N स्वीकार करता है और यदि K स्वीकार करता है तो N अस्वीकार करता है। यदि n, N के इनपुट की लंबाई है, तो m, K के इनपुट की लंबाई n से दोगुनी है और कुछ डेलीमीटर चिह्न भी है, इसलिए m = 2n + 1. N{'}} का चलने का समय इस प्रकार है

{\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right)={\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {2n+1}{2}}\right\rfloor \right)\right)={\mathsf {TIME}}\left(f(n)\right).

अब यदि हम N में इनपुट के रूप में [N] फीड करते हैं जो n को [N] की लंबाई बनाता है और इस प्रकार सवाल पूछते हैं कि क्या N अपने विवरण को इनपुट के रूप में स्वीकार करता है, तो हमें मिलता है,

यदि N 'स्वीकार' करता है [N] जैसा कि हम जानते हैं कि यह अधिकतम f(n) के रूप में संचालन करता है क्योंकि K, f(n) चरणों में ([N], [N]) पर रुकता है, इसका अर्थ है कि K, ([N], [N]) अस्वीकार' करता है इसलिए ([N], [N]) H_f में नहीं होता है और इसी तरह H_f की परिभाषा के अनुसार इसका तात्पर्य यह है कि N, f(n) चरणों के कंट्राडिक्शन [N] को स्वीकार नहीं करता है।

यदि N 'अस्वीकार' करता है [N], जैसा कि हम जानते हैं कि यह अधिकतर f(n) ऑपरेशनों में करता है, इसका अर्थ यह है कि K 'स्वीकार करता है' ([N], [N]), इसलिए ([N], [N]) H_f के रूप में होता है और इस प्रकार N 'f(n) चरणों के कंट्राडिक्शन [N] को स्वीकार नहीं करता है।

इस प्रकार हम यह निष्कर्ष निकालते हैं कि मशीन K के रूप में उपस्थित नहीं है और इसलिए इसे इस प्रकार दिखाया गया है

H_{f}\notin {\mathsf {TIME}}\left(f\left(\left\lfloor {\frac {m}{2}}\right\rfloor \right)\right).

एक्सटेंशन

पाठक ने प्रत्याक्ष किया होगा कि प्रूफ कमजोर परिणाम देता है क्योंकि हमने एक सरल ट्यूरिंग मशीन सिमुलेशन के रूप में चुना है जिसके लिए हम जानते हैं

H_{f}\in {\mathsf {TIME}}(f(m)^{3}).

यह ज्ञात है^[7] एक अधिक कुशल सिमुलेशन के रूप में उपस्थित है, जो इसे स्थापित करता है

H_{f}\in {\mathsf {TIME}}(f(m)\log f(m))

.

गैर-नियतात्मक समय पदानुक्रम प्रमेय

यदि g(n) एक समय-कंस्ट्रक्टिबल फलन है और f(n+1) = o(g(n)), एक डिसिशन प्रॉब्लम के रूप में उपस्थित है, जिसे गैर-नियतात्मक समय f(n) में समाधान नहीं किया जा सकता है, लेकिन गैर-नियतात्मक समय g(n) में समाधान किया जा सकता है और इस प्रकार दूसरे शब्दों में सम्मिश्र वर्ग 'NTIME'(f(n)) 'NTIME'(g(n)) का एक स्ट्रिक्ट् उपसमूह है।

परिणाम

समय पदानुक्रम प्रमेय गारंटी देते हैं कि घातीय पदानुक्रम के नियतात्मक और गैर-नियतात्मक संस्करण वास्तविक पदानुक्रम के रूप में होते है इस प्रकार दूसरे शब्दों में P ⊊ EXPTIME ⊊ 2-EXP ⊊ ... और NP ⊊ NEXPTIME ⊊ 2-NEXP ⊊ ....के रूप में होते है,

उदाहरण के लिए समय पदानुक्रम प्रमेय से ${\mathsf {P}}\subsetneq {\mathsf {EXPTIME}}$ चूँकि ${\mathsf {P}}\subseteq {\mathsf {DTIME}}(2^{n})\subsetneq {\mathsf {DTIME}}(2^{2n})\subseteq {\mathsf {EXPTIME}}$ . वास्तव में,

${\mathsf {DTIME}}\left(2^{n}\right)\subseteq {\mathsf {DTIME}}\left(o\left({\frac {2^{2n}}{2n}}\right)\right)\subsetneq {\mathsf {DTIME}}(2^{2n})$ के रूप में होते है

प्रमेय यह भी गारंटी देता है कि P में ऐसी समस्याएं हैं जिन्हें समाधान करने के लिए मनमाने ढंग से बड़े घातांक की आवश्यकता होती है, इस प्रकार दूसरे शब्दों में किसी भी निश्चित k के लिए ,P DTIME(n^k) तक संक्षिप्त नहीं होता है। उदाहरण के लिए ऐसी समस्याएं हैं जिन्हें n⁵⁰⁰⁰ समय में समाधान किया जा सकता है लेकिन n⁴⁹⁹⁹ समय में समाधान नहीं किया जा सकता है, यह कोबम की थीसिस के विरुद्ध एक लॉजिक्स है, इस प्रकार यह कन्वेंशन P एल्गोरिदम का एक व्यावहारिक वर्ग है। यदि ऐसा कोलेप्स होता है, तो हम यह निष्कर्ष निकाल सकते हैं कि P ≠ PSPACE, क्योंकि यह एक प्रसिद्ध प्रमेय है कि DTIME(f(n)) स्ट्रिक्ट्ली से DSPACE(f(n)) में समाहित हो जाती है।

चूंकि, समय पदानुक्रम प्रमेय नियतात्मक और गैर-नियतात्मक सम्मिश्र समय और स्थान से संबंधित कोई साधन प्रदान नहीं करते हैं, इसलिए वे अभिकलनात्मक सम्मिश्र सिद्धांत के महान अनसुलझे प्रश्नों पर कोई प्रकाश नहीं डालते हैं, यदि P और NP, NP और PSPACE, PSPACE और EXPTIME या EXPTIME और NEXPTIME बराबर हैं या नहीं इस प्रकार देख सकते है।

शार्पर पदानुक्रम प्रमेय

गैप लगभग $\log f(n)$ पदानुक्रम प्रमेय में बंधे निचले और ऊपरी समय के बीच प्रमाण में प्रयुक्त डिवाइस की दक्षता का पता लगाया जा सकता है, अर्थात् एक यूनिवर्सल प्रोग्राम जो चरण- सं संगणना बनाए रखता है। इसे कुछ अभिकलनात्मक मॉडलों पर अधिक कुशलता से किया जा सकता है और इस प्रकार नीचे प्रस्तुत किए गए रिणाम इसके लिए सबसे शार्पर सिद्ध हुए है।

यूनिट-लागत रैंडम एक्सेस मशीन^[8]
एक प्रोग्रामिंग लैंग्वेज मॉडल जिसका प्रोग्राम एक बाइनरी ट्री पर काम करता है जिसे अधिकांशतः इसके रूट के माध्यम से एक्सेस किया जाता है। यह मॉडल नील डी. जोन्स द्वारा प्रस्तुत किया गया है^[9] यह मॉडल नियतात्मक ट्यूरिंग मशीन से अधिक मजबूत है लेकिन रैंडम एक्सेस मशीन से कमजोर है।

इन मॉडलों के लिए, प्रमेय का निम्नलिखित रूप दर्शाया गया'है

यदि f(n) एक समय-कंस्ट्रक्टिबल फलन है, तो एक डिसिशन प्रॉब्लम के रूप में उपस्थित है, जिसे सबसे खराब स्थिति वाले नियतात्मक समय f(n) में समाधान नहीं किया जा सकता है, लेकिन f पर निर्भर कुछ स्थिरांक के लिए इसे सबसे खराब स्थिति वाले समय af(n) में समाधान किया जा सकता है।

इस प्रकार, समय सीमा में एक निरंतर-कारक वृद्धि ट्यूरिंग मशीन की स्थिति के विपरीत अधिक समस्याओं को समाधान करने की अनुमति देती है, रेखीय स्पीडअप प्रमेय में दर्शाया गया'है। इसके अतिरिक्त, बेन-अम्राम ने सिद्ध किया है कि^[10] उपरोक्त मूवल्स में, बहुपद वृद्धि दर के लिए यह स्थिति है कि सभी के लिए $\varepsilon >0$ रैखिक से अधिक एक डिसिशन प्रॉब्लम के रूप में उपस्थित है, जिसे सबसे खराब स्थिति नियतात्मक समय f(n) में समाधान नहीं किया जा सकता है लेकिन इसे समाधान किया जा सकता है सबसे खराब स्थिति वाला समय $(1+\varepsilon )f(n)$ में समाधान किया जा सकता है

यह भी देखें

समष्टि पदानुक्रम प्रमेय

संदर्भ

↑ Hartmanis, J.; Stearns, R. E. (1 May 1965). "On the computational complexity of algorithms". Transactions of the American Mathematical Society. American Mathematical Society. 117: 285–306. doi:10.2307/1994208. ISSN 0002-9947. JSTOR 1994208. MR 0170805.
↑ Hennie, F. C.; Stearns, R. E. (October 1966). "Two-Tape Simulation of Multitape Turing Machines". J. ACM. New York, NY, USA: ACM. 13 (4): 533–546. doi:10.1145/321356.321362. ISSN 0004-5411. S2CID 2347143.
↑ Cook, Stephen A. (1972). "A hierarchy for nondeterministic time complexity". Proceedings of the fourth annual ACM symposium on Theory of computing. STOC '72. Denver, Colorado, United States: ACM. pp. 187–192. doi:10.1145/800152.804913.
↑ Seiferas, Joel I.; Fischer, Michael J.; Meyer, Albert R. (January 1978). "Separating Nondeterministic Time Complexity Classes". J. ACM. New York, NY, USA: ACM. 25 (1): 146–167. doi:10.1145/322047.322061. ISSN 0004-5411. S2CID 13561149.
↑ Žák, Stanislav (October 1983). "A Turing machine time hierarchy". Theoretical Computer Science. Elsevier Science B.V. 26 (3): 327–333. doi:10.1016/0304-3975(83)90015-4.
↑ Fortnow, L.; Santhanam, R. (2004). "Hierarchy Theorems for Probabilistic Polynomial Time". 45th Annual IEEE Symposium on Foundations of Computer Science. p. 316. doi:10.1109/FOCS.2004.33. ISBN 0-7695-2228-9. S2CID 5555450.
↑ Sipser, Michael. संगणना के सिद्धांत का परिचय (3rd ed.). CENGAGE learning. ISBN 1-133-18779-X.
↑ Sudborough, Ivan H.; Zalcberg, A. (1976). "समयबद्ध रैंडम एक्सेस मशीनों द्वारा परिभाषित भाषाओं के परिवारों पर". SIAM Journal on Computing. 5 (2): 217--230. doi:10.1137/0205018.
↑ Jones, Neil D. (1993). "लगातार कारक मायने रखते हैं". 25th Symposium on the theory of Computing: 602–611. doi:10.1145/167088.167244.
↑ Ben-Amram, Amir M. (2003). "सख्त स्थिर-कारक समय पदानुक्रम". Information Processing Letters. 87 (1): 39–44.

अग्रिम पठन

Michael Sipser (1997). Introduction to the Theory of Computation. PWS Publishing. ISBN 0-534-94728-X. Pages 310–313 of section 9.1: Hierarchy theorems.
Christos Papadimitriou (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 0-201-53082-1. Section 7.2: The Hierarchy Theorem, pp. 143–146.

[1] Hartmanis, J.; Stearns, R. E. (1 May 1965). "On the computational complexity of algorithms". Transactions of the American Mathematical Society. American Mathematical Society. 117: 285–306. doi:10.2307/1994208. ISSN 0002-9947. JSTOR 1994208. MR 0170805.

[2] Hennie, F. C.; Stearns, R. E. (October 1966). "Two-Tape Simulation of Multitape Turing Machines". J. ACM. New York, NY, USA: ACM. 13 (4): 533–546. doi:10.1145/321356.321362. ISSN 0004-5411. S2CID 2347143.

[3] Cook, Stephen A. (1972). "A hierarchy for nondeterministic time complexity". Proceedings of the fourth annual ACM symposium on Theory of computing. STOC '72. Denver, Colorado, United States: ACM. pp. 187–192. doi:10.1145/800152.804913.

[4] Seiferas, Joel I.; Fischer, Michael J.; Meyer, Albert R. (January 1978). "Separating Nondeterministic Time Complexity Classes". J. ACM. New York, NY, USA: ACM. 25 (1): 146–167. doi:10.1145/322047.322061. ISSN 0004-5411. S2CID 13561149.

[5] Žák, Stanislav (October 1983). "A Turing machine time hierarchy". Theoretical Computer Science. Elsevier Science B.V. 26 (3): 327–333. doi:10.1016/0304-3975(83)90015-4.

[6] Fortnow, L.; Santhanam, R. (2004). "Hierarchy Theorems for Probabilistic Polynomial Time". 45th Annual IEEE Symposium on Foundations of Computer Science. p. 316. doi:10.1109/FOCS.2004.33. ISBN 0-7695-2228-9. S2CID 5555450.

[7] Sipser, Michael. संगणना के सिद्धांत का परिचय (3rd ed.). CENGAGE learning. ISBN 1-133-18779-X.

[8] Sudborough, Ivan H.; Zalcberg, A. (1976). "समयबद्ध रैंडम एक्सेस मशीनों द्वारा परिभाषित भाषाओं के परिवारों पर". SIAM Journal on Computing. 5 (2): 217--230. doi:10.1137/0205018.

[9] Jones, Neil D. (1993). "लगातार कारक मायने रखते हैं". 25th Symposium on the theory of Computing: 602–611. doi:10.1145/167088.167244.

[10] Ben-Amram, Amir M. (2003). "सख्त स्थिर-कारक समय पदानुक्रम". Information Processing Letters. 87 (1): 39–44.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

@@ Line 1: / Line 1: @@
 {{short description|Given more time, a Turing machine can solve more problems}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत]] में, '''समय हाइरार्की प्रमेय''' [[ट्यूरिंग मशीन]]   पर समयबद्ध गणना के बारे में महत्वपूर्ण कथन हैं। इस प्रकार अनौपचारिक रूप से ये प्रमेय कहती है कि अधिक समय दिए जाने पर ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए ऐसी समस्याएं जिन्हें ''n''<sup>2</sup> समय के साथ हल किया जा सकता है लेकिन n समय के साथ हल नहीं किया जा सकता है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत|अभिकलनात्मक सम्मिश्र सिद्धांत]] में, '''समय पदानुक्रम प्रमेय''' [[ट्यूरिंग मशीन|ट्यूरिंग मशीनों]] पर समयबद्ध संगणना के बारे में महत्वपूर्ण कथन हैं। और अनौपचारिक रूप से ये प्रमेय कहती है कि अधिक समय दिए जाने पर ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए ऐसी समस्याएं जिन्हें ''n''<sup>2</sup> समय के साथ समाधान किया जा सकता है लेकिन n समय के साथ समाधान नहीं किया जा सकता है।
-डिटर्मनिस्टिक मल्टीटेप ट्यूरिंग मशीन  के लिए समय हाइरार्की प्रमेय को पहली बार 1965 में रिचर्ड ई. स्टर्न्स और [[ज्यूरिस हार्टमैनिस]] द्वारा सिद्ध किया गया था।<ref>{{Cite journal
+नियतात्मक मल्टीटेप ट्यूरिंग मशीन के लिए समय पदानुक्रम प्रमेय को पसमाधानी बार 1965 में रिचर्ड ई. स्टर्न्स और [[ज्यूरिस हार्टमैनिस]] द्वारा सिद्ध किया गया था।<ref>{{Cite journal
   | last1 = Hartmanis | first1 = J. | author1-link = Juris Hartmanis
   | last2 = Stearns | first2 = R. E. | author2-link = Richard E. Stearns
@@ Line 16: / Line 16: @@
   | jstor = 1994208| doi-access = free
   }}
-</ref> एक साल बाद इसमें सुधार किया गया जब एफ. सी. हेनी और रिचर्ड ई. स्टर्न्स ने यूनिवर्सल ट्यूरिंग मशीन की दक्षता में सुधार किया था।<ref>{{cite journal
+</ref> एक साल बाद इसमें सुधार किया गया जब एफ. सी. हेनी और रिचर्ड ई. स्टर्न्स ने यूनिवर्सल ट्यूरिंग मशीन की दक्षता में सुधार किया गया था।<ref>{{cite journal
 | last1        = Hennie
 | first1       = F. C.
@@ Line 32: / Line 32: @@
 | issn         = 0004-5411
 | doi          = 10.1145/321356.321362| s2cid = 2347143
-}}</ref> और इस प्रकार प्रमेय के परिणामस्वरूप प्रत्येक डिटर्मनिस्टिक समय-सीमाबद्ध [[जटिलता वर्ग|कॉम्प्लेक्सिटी वर्ग]] के लिए एक सख्ती से बड़ा समय-सीमाबद्ध कॉम्प्लेक्सिटी वर्ग होता है और इसलिए कॉम्प्लेक्सिटी वर्गों की समय-सीमाबद्ध हाइरार्की पूरी तरह से नष्ट नहीं होता है। इस प्रकार अधिक सटीक रूप से, डिटर्मनिस्टिक ट्यूरिंग मशीन  के लिए समय हाइरार्की प्रमेय बताता है कि सभी रचनात्मक फ़ंक्शन के लिए समय कंस्ट्रक्टिबल फ़ंक्शन f(n) के रूप में है।
+}}</ref> और इस प्रकार प्रमेय के परिणामस्वरूप प्रत्येक नियतात्मक समय-सीमाबद्ध [[जटिलता वर्ग|सम्मिश्र वर्ग]] के लिए स्ट्रिक्टली से बड़ा सम्मिश्र वर्ग है और इसलिए सम्मिश्र वर्ग की समय-सीमाबद्ध में पदानुक्रम पूरी तरह से नष्ट नहीं होता है और इस प्रकार अधिक सटीक रूप से नियतात्मक ट्यूरिंग मशीन के लिए समय पदानुक्रम प्रमेय बताता है कि सभी रचनात्मक फलन के लिए समय कंस्ट्रक्टिबल फलन f(n) है।
 :<math>\mathsf{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right) \subsetneq \mathsf{DTIME}(f(n))</math>,
-जहां [[DTIME]] (f(n)) समय O, (f(n)) में हल करने योग्य [[निर्णय समस्याओं]] की कॉम्प्लेक्सिटी वर्ग को दर्शाता है।
+जहां [[DTIME]] (f(n)) समय O, (f(n)) में व्याख्या करने योग्य [[निर्णय समस्याओं|डिसिशन समस्याओं]] की सम्मिश्र वर्ग को दर्शाता है। ध्यान दें कि बाएं हाथ के वर्ग में बहुत कम O अंकन पद्धति के रूप में सम्मलित है, जो कि ''f''(''n'') समय से कम समय में सोल्वेबल निर्णय समस्याओं के समुच्चय को संदर्भित करता है।
-[[गैर-नियतात्मक ट्यूरिंग मशीन|गैर-डिटर्मनिस्टिक ट्यूरिंग]] मशीन  के लिए समय हाइरार्की प्रमेय मूल रूप से 1972 में [[स्टीफन कुक]] द्वारा सिद्ध किया गया था।<ref>{{cite conference
+[[गैर-नियतात्मक ट्यूरिंग मशीन|गैर-नियतात्मक ट्यूरिंग]] मशीन के लिए समय पदानुक्रम प्रमेय मूल रूप से 1972 में [[स्टीफन कुक]] द्वारा सिद्ध किया गया था।<ref>{{cite conference
 | title         = A hierarchy for nondeterministic time complexity
 | first         = Stephen A.
@@ Line 50: / Line 48: @@
 | pages         = 187–192
 | doi           = 10.1145/800152.804913| doi-access= free
-}}</ref> 1978 में जोएल सेफेरस, माइकल जे. फिशर और अल्बर्ट आर. मेयर द्वारा एक कॉम्प्लेक्सिटी प्रमाण के माध्यम से इसे इसके वर्तमान स्वरूप में सुधार किया जाता है।<ref>{{cite journal
+}}</ref> वर्ष 1978 में जोएल सेफेरस, माइकल जे. फिशर और अल्बर्ट आर. मेयर द्वारा एक सम्मिश्र प्रमाण के माध्यम से इसके वर्तमान स्वरूप में सुधार किया गया है।<ref>{{cite journal
 | last1        = Seiferas
 | first1       = Joel I.
@@ Line 69: / Line 67: @@
 | issn         = 0004-5411
 | doi          = 10.1145/322047.322061| s2cid = 13561149
-}}</ref> और इस प्रकार विशेष रूप में 1983 में, स्टैनिस्लाव ज़ैक ने आज भी साधारण प्रमाण के साथ वही परिणाम प्राप्त किया था।<ref>{{cite journal
+}}</ref> और इस प्रकार विशेष रूप में वर्ष 1983 में, स्टैनिस्लाव ज़ैक ने साधारण प्रमाण के साथ वही परिणाम प्राप्त किये थे।<ref>{{cite journal
 | first1        = Stanislav
 | last1       = Žák
@@ Line 80: / Line 78: @@
 | publisher    = Elsevier Science B.V.
 | doi          = 10.1016/0304-3975(83)90015-4| doi-access= free
-}}</ref> इस प्रकार गैर-डिटर्मनिस्टिक ट्यूरिंग मशीन  के लिए समय हाइरार्की प्रमेय बताता है कि यदि g(n) एक समय कंस्ट्रक्टिबल फ़ंक्शन f(n+1) = o(g(n)) के रूप में होता है,
+}}</ref> जो गैर-नियतात्मक ट्यूरिंग मशीन के लिए समय पदानुक्रम प्रमेय बताता है कि यदि g(n) समय कंस्ट्रक्टिबल फलन f(n+1) = o(g(n)) के रूप में है,
 :<math>\mathsf{NTIME}(f(n)) \subsetneq \mathsf{NTIME}(g(n))</math>.
-किसी क्षेत्र के लिए एनालॉग प्रमेय [[अंतरिक्ष पदानुक्रम प्रमेय|स्थान हाइरार्की प्रमेय]] के रूप में हैं। इस प्रकार एक समान प्रमेय समयबद्ध प्रोबबिलिस्टिक कॉम्प्लेक्सिटी वर्गों के लिए ज्ञात नहीं है, जब तक कि वर्ग के पास कॉम्प्लेक्सिटी का एक बिट भी न हो।<ref>{{Cite book|doi=10.1109/FOCS.2004.33|title=45th Annual IEEE Symposium on Foundations of Computer Science|year=2004|author=Fortnow, L.|pages=316|last2=Santhanam|first2=R.|chapter=Hierarchy Theorems for Probabilistic Polynomial Time|isbn=0-7695-2228-9|s2cid=5555450}}</ref>
+किसी समष्टि के लिए एनालॉग प्रमेय [[अंतरिक्ष पदानुक्रम प्रमेय|समष्टि पदानुक्रम प्रमेय]] के रूप में होती हैं। इस प्रकार एक समान प्रमेय समयबद्ध प्रोबबिलिस्टिक सम्मिश्र वर्ग के लिए ज्ञात नहीं है, जब तक कि वर्ग के पास सम्मिश्र के रूप में एक भी बिट उपलब्ध न हो।<ref>{{Cite book|doi=10.1109/FOCS.2004.33|title=45th Annual IEEE Symposium on Foundations of Computer Science|year=2004|author=Fortnow, L.|pages=316|last2=Santhanam|first2=R.|chapter=Hierarchy Theorems for Probabilistic Polynomial Time|isbn=0-7695-2228-9|s2cid=5555450}}</ref>
 ==पृष्ठभूमि==
-दोनों प्रमेय एक रचनात्मक फ़ंक्शन | समय-कंस्ट्रक्टिबल  फ़ंक्शन की धारणा का उपयोग करते हैं। एक [[फ़ंक्शन (गणित)]] <math>f:\mathbb{N}\rightarrow\mathbb{N}</math> समय-कंस्ट्रक्टिबल  है यदि प्रत्येक के लिए ऐसी डिटर्मनिस्टिक ट्यूरिंग मशीन मौजूद है <math>n\in\mathbb{N}</math>, यदि मशीन को n वाले इनपुट के साथ शुरू किया जाता है, तो यह ठीक f(n) चरणों के बाद रुक जाएगी। गैर-ऋणात्मक पूर्णांक गुणांक वाले सभी [[बहुपद]] समय-कंस्ट्रक्टिबल  हैं, जैसे कि 2 जैसे घातीय कार्य हैं<sup>n</sup>.
+दोनों प्रमेयों एक समय कंस्ट्रक्टिबल फलन की नोशन का उपयोग करते हैं। एक [[फ़ंक्शन (गणित)|फलन (गणित)]] <math>f:\mathbb{N}\rightarrow\mathbb{N}</math> समय-कंस्ट्रक्टिबल के रूप में है, यदि कोई नियतात्मक ट्यूरिंग मशीन के रूप में उपस्थित है जैसे कि प्रत्येक ,<math>n\in\mathbb{N}</math>, के रूप मेंहोते है, यदि मशीन को n वाले इनपुट के साथ शुरू किया जाता है, तो यह ठीक f(n) चरणों के बाद रुक जाती है और इस प्रकार गैर-ऋणात्मक पूर्णांक गुणांक वाले सभी [[बहुपद]] समय-कंस्ट्रक्टिबल के रूप में होते है, जैसे कि 2<sup>n</sup> जैसे घातीय फलन के रूप में होते है
-==प्रमाण सिंहावलोकन==
+==प्रमाण अवलोकन==
-हमें यह साबित करने की जरूरत है कि कुछ समय वर्ग TIME(''g''(''n'')) कुछ समय वर्ग TIME(''f''(''n'')) से बिल्कुल बड़ा है। हम एक ऐसी मशीन का निर्माण करके ऐसा करते हैं जो कैंटर के विकर्ण तर्क द्वारा TIME(''f''(''n'')) में नहीं हो सकती। फिर हम सिमुलेशन#कंप्यूटर विज्ञान का उपयोग करके दिखाते हैं कि मशीन TIME(''g''(''n'')) में है।
+हमें यह सिद्ध करने की आवश्यकता है कि कुछ समय वर्ग TIME(''g''(''n'')) कुछ समय वर्ग TIME(''f''(''n'')) से पूर्णतः बड़ा होता है। हम एक ऐसी मशीन का निर्माण करके ऐसा करते हैं जो कैंटर के विकर्ण लॉजिक्स द्वारा TIME(''f''(''n'')) में नहीं हो सकती है। फिर हम सिमुलेशन मशीन का उपयोग करके दिखाते हैं कि मशीन TIME(''g''(''n'')) के रूप में होती है।
-==डिटर्मनिस्टिक समय हाइरार्की प्रमेय==
+==नियतात्मक समय पदानुक्रम प्रमेय==
 ===कथन===
-<ब्लॉककोट>समय हाइरार्की प्रमेय। यदि ''f''(''n'') एक समय-कंस्ट्रक्टिबल  कार्य है, तो एक निर्णय समस्या मौजूद है जिसे सबसे खराब स्थिति वाले डिटर्मनिस्टिक समय ''f''(''n'') में हल नहीं किया जा सकता है, लेकिन सबसे खराब स्थिति वाले डिटर्मनिस्टिक समय में इसे ''f''(''n'')log ''f''(''n'') से बड़े आकार में हल किया जा सकता है। उदाहरण के लिए,
+समय पदानुक्रम प्रमेय, यदि ''f''(''n'') समय-कंस्ट्रक्टिबल फलन है, तो एक डिसिशन प्रॉब्लम के रूप में उपस्थित है जिसे सबसे खराब स्थिति वाले नियतात्मक समय ''f''(''n'') में समाधान नहीं किया जा सकता है, लेकिन सबसे खराब स्थिति वाले नियतात्मक समय में इसे ''f''(''n'')log ''f''(''n'') से बड़े आकार में समाधान किया जा सकता है। उदाहरण इस प्रकार है,
-:<math>\mathsf{DTIME}(f(n)) \subsetneq \mathsf{DTIME}\left (f(n)\log^2 f(n) \right).</math></ब्लॉककोट>
+:<math>\mathsf{DTIME}(f(n)) \subsetneq \mathsf{DTIME}\left (f(n)\log^2 f(n) \right).</math>
-नोट 1. ''f''(''n'') कम से कम ''n'' है, क्योंकि छोटे फ़ंक्शन कभी भी समय-कंस्ट्रक्टिबल  नहीं होते हैं।<br>
+नोट 1. ''f''(''n'') कम से कम ''n'' है, क्योंकि छोटे फलन कभी भी समय-कंस्ट्रक्टिबल नहीं होते हैं।<br>
-नोट 2. एल्गोरिदम का सटीक विवरण निम्न प्रकार से छोटे ओ का उपयोग करके लिखा जा सकता है: यदि ''एफ''(''एन'') समय-रचना योग्य है, तो
+नोट 2. एल्गोरिदम का सटीक विवरण निम्न प्रकार से छोटे फलन का उपयोग करके लिखा जा सकता है, यदि ''f''(''n'') समय-कंस्ट्रक्टिबल है, तो
 :<math>\mathsf{DTIME}\left(o\left(\frac{f(n)}{\log f(n)}\right)\right)\subsetneq \mathsf{DTIME}\left (f(n) \right).</math>
-उदाहरण के लिए, टाइम एनलॉग में हल करने योग्य समस्याएं हैं<sup>2</sup>n लेकिन समय और नहीं, स्थान n अंदर है
+उदाहरण के लिए, टाइम एनलॉग में सोल्वेबल समस्याएं ''n''log<sup>2</sup>''n'' के रूप में होती है, लेकिन समय n अंदर है लेकिन समय n के रूप में नहीं होती है, यह <math>{\displaystyle f(n)=n\log n}</math> समुच्चयिंग के बाद आता है चूंकि n <math>{\displaystyle o\left(n\log n\right).}</math>के रूप में होता है,
-:<math>o\left(\frac{n\log^2 n}{\log {(n\log^2 n)}}\right).</math>
 ===प्रमाण===
-हम यहां एक कमजोर परिणाम का प्रमाण शामिल करते हैं, अर्थात् DTIME(''f''(''n'')) DTIME(''f''(2''n'' + 1) का एक सख्त उपसमुच्चय है<sup>3</sup>), क्योंकि यह सरल है लेकिन प्रमाण विचार को दर्शाता है। सबूत को f(n)logf(n) तक कैसे बढ़ाया जाए, इसकी जानकारी के लिए इस अनुभाग के नीचे देखें।
+हम यहां एक विकर्स रिजल्ट्स का प्रूफ सम्मलित करते हैं, अर्थात् DTIME(''f''(''n'')), DTIME(''f''(2''n'' + 1) का एक स्ट्रिक्ट्ली उपसमूह है, क्योंकि यह सरल है लेकिन प्रूफ विचार को दर्शाता है। प्रूफ को f(n)logf(n) तक कैसे बढ़ाया जाए, इसकी जानकारी के लिए इस अनुभाग के नीचे दिखाया जाता है।
-इसे साबित करने के लिए, हम पहले मशीन  की एन्कोडिंग और उनके इनपुट की भाषा को परिभाषित करते हैं जो उन्हें एफ के भीतर रुकने का कारण बनता है
+इसे सिद्ध करने के लिए, हम पसमाधाने मशीन की एन्कोडिंग और उनके इनपुट की लैंग्वेज को परिभाषित करते हैं जो उन्हें f के भीतर रुकने का कारण बनता है
 : <math> H_f = \left\{ ([M], x)\ |\ M \ \text{accepts}\ x \ \text{in}\ f(|x|) \ \text{steps} \right\}. </math>
-यहां ध्यान दें कि यह एक समय-वर्ग है। यह उन मशीन  (M,x) के लिए मशीन  और इनपुट के जोड़े का सेट है ताकि मशीन M f(|x|) चरणों के भीतर स्वीकार कर सके।
+यहां ध्यान दें कि यह एक समय-वर्ग है। यह उन मशीन (M,x) के लिए मशीन और इनपुट के जोड़े का समुच्चय है जिससे कि मशीन M f(|x|) चरणों के भीतर स्वीकार करते है।
-यहां, एम एक डिटर्मनिस्टिक ट्यूरिंग मशीन है, और एक्स इसका इनपुट (इसके टेप की प्रारंभिक सामग्री) है। [एम] एक इनपुट को दर्शाता है जो ट्यूरिंग मशीन एम को एनकोड करता है। मान लीजिए कि एम टुपल का आकार है ([एम], एक्स)।
+यहां, M एक नियतात्मक ट्यूरिंग मशीन है और x इसका इनपुट है और इसके टेप की प्रारंभिक सामग्री है। [M ] एक इनपुट को दर्शाता है, जो ट्यूरिंग मशीन M को एनकोड करता है। मान लीजिए कि M टुपल का आकार ([''M''], ''x'') के रूप में है।
-हम जानते हैं कि हम एच की सदस्यता तय कर सकते हैं<sub>f</sub>एक डिटर्मनिस्टिक ट्यूरिंग मशीन आर के माध्यम से, जो पहले एफ (| प्रत्येक चरण में, अगली कार्रवाई क्या होगी, यह तय करने के लिए सिमुलेशन मशीन को एम की परिभाषा को देखने की जरूरत है। यह कहना सुरक्षित है कि इसमें अधिकतम f(m) लगता है<sup>3</sup> संचालन (चूंकि यह ज्ञात है कि समय कॉम्प्लेक्सिटी T(n) की मशीन का अनुकरण समय में प्राप्त किया जा सकता है <math>O(T(n)\cdot|M|)</math> एक मल्टीटेप मशीन पर, जहाँ |M| एम की एन्कोडिंग की लंबाई है), हमारे पास वह है:
+हम जानते हैं कि हम नियतात्मक ट्यूरिंग मशीन R के माध्यम से H<sub>f</sub> की मेम्बरशिप तय कर सकते हैं और जो पसमाधाने f(|x|) की सं संगणना करके और फिर उस लंबाई की 0s की एक पंक्ति लिखकर और फिर इसका उपयोग करके f(x) चरणों के लिए M का अनुकरण करती है। और इस प्रकार अधिकतम इतने चरणों के लिए M का अनुकरण करने के लिए एक घड़ी या काउंटर के रूप में 0s की पंक्ति के रूप में अनुकरण करती है, प्रत्येक चरण में, अगली कार्रवाई क्या होगी, यह तय करने के लिए सिमुलेशन मशीन को M की परिभाषा को देखने की जरूरत है। यह कहना सुरक्षित है कि इसमें अधिकतम f(m)<sup>3</sup> ऑपरेशन लगते हैं, क्योंकि यह ज्ञात है कि समय सम्मिश्र T(n) की मशीन का अनुकरण एक मल्टीटेप मशीन पर समय <math>O(T(n)\cdot|M|)</math> में प्राप्त किया जा सकता है, जहाँ |M| M की एन्कोडिंग की लंबाई है हमारे पास है
 : <math> H_f \in \mathsf{TIME}\left(f(m)^3\right). </math>
-बाकी सबूत यह दिखा देंगे
+शेष प्रूफ इस प्रकार दिखा देंते है
 : <math> H_f \notin \mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right) </math>
-ताकि यदि हम m के स्थान पर 2n + 1 प्रतिस्थापित करें, तो हमें वांछित परिणाम प्राप्त हो। आइए मान लें कि एच<sub>f</sub>इस समय कॉम्प्लेक्सिटी वर्ग में है, और हम एक विरोधाभास पर पहुंच जाएंगे।
+जिससे कि यदि हम m के स्थान पर 2n + 1 प्रतिस्थापित करते है, तो हमें वांछित परिणाम प्राप्त होते है। आइए मान लें H<sub>f</sub> की इस समय सम्मिश्र वर्ग है और हम एक अन्तर्विरोध पर पहुंच जाते है।
-यदि एच<sub>f</sub>इस समय कॉम्प्लेक्सिटी वर्ग में है, तो वहां एक मशीन K मौजूद है, जो कुछ मशीन विवरण [M] और इनपुट x दिए जाने पर यह तय करती है कि टुपल ([M], x) H में है या नहीं<sub>f</sub>अंदर
+यदि H<sub>f</sub> इस समय सम्मिश्र वर्ग में है, तो वहां एक मशीन K के रूप में उपस्थित है, जो कुछ मशीन विवरण [M] और इनपुट x दिए जाने पर यह तय करती है कि टुपल ([M], x) H<sub>f</sub> के रूप में उपस्थित है
 :<math>\mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right). </math>
-हम इस K का उपयोग एक अन्य मशीन, N के निर्माण के लिए करते हैं, जो एक मशीन विवरण [M] लेती है और K को टुपल ([M], [M]) पर चलाती है, अर्थात। M को K द्वारा अपने स्वयं के कोड पर सिम्युलेटेड किया गया है, और यदि K अस्वीकार करता है तो N स्वीकार करता है, और यदि K स्वीकार करता है तो N अस्वीकार करता है।
+<nowiki>हम इस K का उपयोग एक अन्य मशीन N के निर्माण के लिए करते हैं, जो एक मशीन विवरण [M] के रूप में होती है और K को टुपल ([M], [M]) पर चलाती है, अर्थात M को K द्वारा अपने स्वयं के कोड पर सिम्युलेटेड किया जाता है और यदि K अस्वीकार करता है तो N स्वीकार करता है और यदि K स्वीकार करता है तो N अस्वीकार करता है। यदि n, N के इनपुट की लंबाई है, तो m, K के इनपुट की लंबाई n से दोगुनी है और कुछ डेलीमीटर चिह्न भी है, इसलिए m = 2n + 1. N{'}} का चलने का समय इस प्रकार है</nowiki>
-यदि n, N के इनपुट की लंबाई है, तो m (K के इनपुट की लंबाई) n से दोगुना और कुछ सीमांकक चिह्न है, इसलिए m = 2n + 1. N{'}} का चलने का समय इस प्रकार है
 :<math> \mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right) = \mathsf{TIME}\left(f\left( \left\lfloor \frac{2n+1}{2} \right\rfloor \right)\right) = \mathsf{TIME}\left(f(n)\right). </math>
-अब यदि हम एन में ही इनपुट के रूप में [एन] फीड करते हैं (जो एन को [एन] की लंबाई बनाता है) और सवाल पूछते हैं कि क्या एन अपने विवरण को इनपुट के रूप में स्वीकार करता है, तो हमें मिलता है:
+अब यदि हम N में इनपुट के रूप में [N] फीड करते हैं जो n को [N] की लंबाई बनाता है और इस प्रकार सवाल पूछते हैं कि क्या N अपने विवरण को इनपुट के रूप में स्वीकार करता है, तो हमें मिलता है,
-* यदि N 'स्वीकार' करता है [N] (जैसा कि हम जानते हैं कि यह अधिकतम f(n) संचालन में करता है क्योंकि K, f(n) चरणों में ([N], [N]) पर रुकता है), इसका मतलब है कि K 'अस्वीकार' करता है ([N], [N]), इसलिए ([N], [N]) H में नहीं है<sub>f</sub>, और इसी तरह एच की परिभाषा के अनुसार<sub>f</sub>, इसका तात्पर्य यह है कि N, f(n) चरणों में [N] को स्वीकार नहीं करता है। विरोधाभास।
-* यदि N 'अस्वीकार' करता है [N] (जैसा कि हम जानते हैं कि यह अधिकतर f(n) ऑपरेशनों में करता है), इसका मतलब यह है कि K 'स्वीकार करता है' ([N], [N]), इसलिए ([N], [N]) H में 'है'<sub>f</sub>, और इस प्रकार N 'f(n) चरणों में [N] को स्वीकार करता है। विरोधाभास।
+* यदि N 'स्वीकार' करता है [N] जैसा कि हम जानते हैं कि यह अधिकतम f(n) के रूप में संचालन करता है क्योंकि K, f(n) चरणों में ([N], [N]) पर रुकता है, इसका अर्थ है कि K, ([N], [N]) अस्वीकार' करता है इसलिए ([N], [N]) H<sub>f</sub> में नहीं होता है और इसी तरह H<sub>f</sub> की परिभाषा के अनुसार इसका तात्पर्य यह है कि N, f(n) चरणों के कंट्राडिक्शन [N] को स्वीकार नहीं करता है।
-इस प्रकार हम यह निष्कर्ष निकालते हैं कि मशीन K मौजूद नहीं है, और इसलिए
+* यदि N 'अस्वीकार' करता है [N], जैसा कि हम जानते हैं कि यह अधिकतर f(n) ऑपरेशनों में करता है, इसका अर्थ यह है कि K 'स्वीकार करता है' ([N], [N]), इसलिए ([N], [N]) H<sub>f</sub> के रूप में होता है और इस प्रकार N 'f(n) चरणों के कंट्राडिक्शन [N] को स्वीकार नहीं करता है।
+इस प्रकार हम यह निष्कर्ष निकालते हैं कि मशीन K के रूप में उपस्थित नहीं है और इसलिए इसे इस प्रकार दिखाया गया है
 : <math> H_f \notin \mathsf{TIME}\left(f\left( \left\lfloor \frac{m}{2} \right\rfloor \right)\right). </math>
-===विस्तार===
+===एक्सटेंशन===
-पाठक ने महसूस किया होगा कि प्रमाण कमजोर परिणाम देता है क्योंकि हमने एक सरल ट्यूरिंग मशीन सिमुलेशन चुना है जिसके लिए हम जानते हैं
+पाठक ने प्रत्याक्ष किया होगा कि प्रूफ कमजोर परिणाम देता है क्योंकि हमने एक सरल ट्यूरिंग मशीन सिमुलेशन के रूप में चुना है जिसके लिए हम जानते हैं
 : <math> H_f \in \mathsf{TIME}(f(m)^3). </math>
-यह ज्ञात है<ref>{{cite book |last1=Sipser |first1=Michael |title=संगणना के सिद्धांत का परिचय|publisher=CENGAGE learning |isbn=1-133-18779-X |edition=3rd}}</ref> एक अधिक कुशल सिमुलेशन मौजूद है जो इसे स्थापित करता है
+यह ज्ञात है<ref>{{cite book |last1=Sipser |first1=Michael |title=संगणना के सिद्धांत का परिचय|publisher=CENGAGE learning |isbn=1-133-18779-X |edition=3rd}}</ref> एक अधिक कुशल सिमुलेशन के रूप में उपस्थित है, जो इसे स्थापित करता है
 : <math> H_f \in \mathsf{TIME}(f(m) \log f(m)) </math>.
-==गैर-डिटर्मनिस्टिक [[समय]] हाइरार्की प्रमेय==
+==गैर-नियतात्मक [[समय]] पदानुक्रम प्रमेय==
-यदि g(n) एक समय-कंस्ट्रक्टिबल  फ़ंक्शन है, और f(n+1) = बिग O नोटेशन(g(n)), तो एक निर्णय समस्या मौजूद है जिसे गैर-डिटर्मनिस्टिक समय f(n) में हल नहीं किया जा सकता है, लेकिन गैर-डिटर्मनिस्टिक समय g(n) में हल किया जा सकता है। दूसरे शब्दों में, कॉम्प्लेक्सिटी वर्ग 'NTIME'(f(n)) 'NTIME'(g(n)) का एक सख्त उपसमुच्चय है।
+यदि g(n) एक समय-कंस्ट्रक्टिबल फलन है और ''f''(''n''+1) = o(''g''(''n'')), एक डिसिशन प्रॉब्लम के रूप में उपस्थित है, जिसे गैर-नियतात्मक समय f(n) में समाधान नहीं किया जा सकता है, लेकिन गैर-नियतात्मक समय g(n) में समाधान किया जा सकता है और इस प्रकार दूसरे शब्दों में सम्मिश्र वर्ग 'NTIME'(f(n)) 'NTIME'(g(n)) का एक स्ट्रिक्ट् उपसमूह है।
 ==परिणाम==
-समय हाइरार्की प्रमेय गारंटी देते हैं कि [[घातीय पदानुक्रम|घातीय]] हाइरार्की के डिटर्मनिस्टिक और गैर-डिटर्मनिस्टिक संस्करण वास्तविक हाइरार्की हैं: दूसरे शब्दों में [[पी (जटिलता)]] ⊊ [[EXPTIME]] ⊊ [[2-EXP]] ⊊ ... और NP (जटिलता) ⊊ [[NEXPTIME]] ⊊ 2-NEXP ⊊ ....
+समय पदानुक्रम प्रमेय गारंटी देते हैं कि [[घातीय पदानुक्रम|घातीय]] पदानुक्रम के नियतात्मक और गैर-नियतात्मक संस्करण वास्तविक पदानुक्रम के रूप में होते है इस प्रकार दूसरे शब्दों में '''P''' ⊊ '''EXPTIME''' ⊊ '''2-EXP''' ⊊ ... और '''NP''' ⊊ '''NEXPTIME''' ⊊ '''2-NEXP''' ⊊ ....के रूप में होते है,
+उदाहरण के लिए समय पदानुक्रम प्रमेय से <math>\mathsf{P} \subsetneq \mathsf{EXPTIME}</math> चूँकि <math>\mathsf{P} \subseteq \mathsf{DTIME} (2^n)\subsetneq  \mathsf{DTIME} (2^{2n}) \subseteq \mathsf{EXPTIME}</math>. वास्तव में,
-उदाहरण के लिए, <math>\mathsf{P} \subsetneq \mathsf{EXPTIME}</math> तब से <math>\mathsf{P} \subseteq \mathsf{DTIME} (2^n)\subsetneq  \mathsf{DTIME} (2^{2n}) \subseteq \mathsf{EXPTIME}</math>. वास्तव में, <math>\mathsf{DTIME}\left(2^n\right) \subseteq \mathsf{DTIME}\left(o\left(\frac{2^{2n}}{2n}\right)\right) \subsetneq \mathsf{DTIME}(2^{2n})</math> समय हाइरार्की प्रमेय से.
+<math>\mathsf{DTIME}\left(2^n\right) \subseteq \mathsf{DTIME}\left(o\left(\frac{2^{2n}}{2n}\right)\right) \subsetneq \mathsf{DTIME}(2^{2n})</math> के रूप में होते है
-प्रमेय यह भी गारंटी देता है कि पी में ऐसी समस्याएं हैं जिन्हें हल करने के लिए मनमाने ढंग से बड़े घातांक की आवश्यकता होती है; दूसरे शब्दों में, P DTIME(''n'' तक संक्षिप्त नहीं होता है<sup>k</sup>) किसी निश्चित k के लिए। उदाहरण के लिए, n में हल करने योग्य समस्याएं हैं<sup>5000</sup>समय लेकिन n नहीं<sup>4999</sup>समय. यह कोबम की थीसिस के ख़िलाफ़ एक तर्क है, यह परंपरा कि पी एल्गोरिदम का एक व्यावहारिक वर्ग है। यदि ऐसा पतन होता है, तो हम यह निष्कर्ष निकाल सकते हैं कि P ≠ [[PSPACE]], क्योंकि यह एक प्रसिद्ध प्रमेय है कि DTIME(''f''(''n'')) सख्ती से DSPACE(''f''(''n'')) में समाहित है।
+प्रमेय यह भी गारंटी देता है कि '''P''' में ऐसी समस्याएं हैं जिन्हें समाधान करने के लिए मनमाने ढंग से बड़े घातांक की आवश्यकता होती है, इस प्रकार दूसरे शब्दों में किसी भी निश्चित k के लिए ,'''P''' '''DTIME'''(''n<sup>k</sup>'') तक संक्षिप्त नहीं होता है। उदाहरण के लिए ऐसी समस्याएं हैं जिन्हें n<sup>5000</sup> समय में समाधान किया जा सकता है लेकिन n<sup>4999</sup> समय में समाधान नहीं किया जा सकता है, यह कोबम की थीसिस के विरुद्ध एक लॉजिक्स है, इस प्रकार यह कन्वेंशन '''P''' एल्गोरिदम का एक व्यावहारिक वर्ग है। यदि ऐसा कोलेप्स होता है, तो हम यह निष्कर्ष निकाल सकते हैं कि P ≠ [[PSPACE]], क्योंकि यह एक प्रसिद्ध प्रमेय है कि DTIME(''f''(''n'')) स्ट्रिक्ट्ली से DSPACE(''f''(''n'')) में समाहित हो जाती है।
-हालाँकि, समय हाइरार्की प्रमेय डिटर्मनिस्टिक और गैर-डिटर्मनिस्टिक जटिलता, या समय और स्थान कॉम्प्लेक्सिटी से संबंधित कोई साधन प्रदान नहीं करते हैं, इसलिए वे कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत के महान अनसुलझे प्रश्नों पर कोई प्रकाश नहीं डालते हैं: क्या P = NP समस्या, NP और PSPACE, PSPACE और EXPTIME, या EXPTIME और NEXPTIME समान हैं या नहीं।
+चूंकि, समय पदानुक्रम प्रमेय नियतात्मक और गैर-नियतात्मक सम्मिश्र समय और स्थान से संबंधित कोई साधन प्रदान नहीं करते हैं, इसलिए वे अभिकलनात्मक सम्मिश्र सिद्धांत के महान अनसुलझे प्रश्नों पर कोई प्रकाश नहीं डालते हैं, यदि P और NP, NP और PSPACE, PSPACE और EXPTIME या EXPTIME और NEXPTIME बराबर हैं या नहीं इस प्रकार देख सकते है।
-==तीव्र हाइरार्की प्रमेय==
+==शार्पर पदानुक्रम प्रमेय==
-का अंतर लगभग <math>\log f(n)</math> हाइरार्की प्रमेय में बंधे निचले और ऊपरी समय के बीच प्रमाण में प्रयुक्त डिवाइस की दक्षता का पता लगाया जा सकता है, अर्थात् एक सार्वभौमिक कार्यक्रम जो चरण-गणना बनाए रखता है। इसे कुछ कम्प्यूटेशनल मॉडलों पर अधिक कुशलता से किया जा सकता है। नीचे प्रस्तुत किए गए सबसे तीव्र परिणाम इसके लिए सिद्ध हुए हैं:
+गैप लगभग <math>\log f(n)</math> पदानुक्रम प्रमेय में बंधे निचले और ऊपरी समय के बीच प्रमाण में प्रयुक्त डिवाइस की दक्षता का पता लगाया जा सकता है, अर्थात् एक यूनिवर्सल प्रोग्राम जो चरण- सं संगणना बनाए रखता है। इसे कुछ अभिकलनात्मक मॉडलों पर अधिक कुशलता से किया जा सकता है और इस प्रकार नीचे प्रस्तुत किए गए रिणाम इसके लिए सबसे शार्पर सिद्ध हुए है।
 * यूनिट-लागत [[रैंडम एक्सेस मशीन]]<ref>{{cite journal |last1=Sudborough |first1=Ivan H. |last2=Zalcberg |first2=A. |title=समयबद्ध रैंडम एक्सेस मशीनों द्वारा परिभाषित भाषाओं के परिवारों पर|journal=SIAM Journal on Computing |date=1976 |volume=5 |issue=2 |pages=217--230 |doi=10.1137/0205018}}</ref>
-* एक [[प्रोग्रामिंग भाषा]] मॉडल जिसका प्रोग्राम एक बाइनरी ट्री पर काम करता है जिसे हमेशा इसके रूट के माध्यम से एक्सेस किया जाता है। यह मॉडल, नील डी. जोन्स द्वारा प्रस्तुत किया गया<ref>{{cite journal |last1=Jones |first1=Neil D. |title=लगातार कारक मायने रखते हैं|journal=25th Symposium on the theory of Computing |date=1993 |pages=602-611 |doi=10.1145/167088.167244}}</ref> डिटर्मनिस्टिक ट्यूरिंग मशीन से अधिक मजबूत है लेकिन रैंडम एक्सेस मशीन से कमजोर है।
+* एक [[प्रोग्रामिंग भाषा|प्रोग्रामिंग]] लैंग्वेज मॉडल जिसका प्रोग्राम एक बाइनरी ट्री पर काम करता है जिसे अधिकांशतः इसके रूट के माध्यम से एक्सेस किया जाता है। यह मॉडल नील डी. जोन्स द्वारा प्रस्तुत किया गया है<ref>{{cite journal |last1=Jones |first1=Neil D. |title=लगातार कारक मायने रखते हैं|journal=25th Symposium on the theory of Computing |date=1993 |pages=602-611 |doi=10.1145/167088.167244}}</ref> यह मॉडल नियतात्मक ट्यूरिंग मशीन से अधिक मजबूत है लेकिन रैंडम एक्सेस मशीन से कमजोर है।
-इन मॉडलों के लिए, प्रमेय का निम्नलिखित रूप है:
+इन मॉडलों के लिए, प्रमेय का निम्नलिखित रूप दर्शाया गया'है
-<blockquote>यदि f(n) एक समय-कंस्ट्रक्टिबल  फ़ंक्शन है, तो एक निर्णय समस्या मौजूद है जिसे सबसे खराब स्थिति वाले डिटर्मनिस्टिक समय f(n) में हल नहीं किया जा सकता है, लेकिन कुछ स्थिरांक a (f पर निर्भर) के लिए सबसे खराब स्थिति वाले समय af(n) में हल किया जा सकता है।</blockquote>
+<blockquote>यदि f(n) एक समय-कंस्ट्रक्टिबल फलन है, तो एक डिसिशन प्रॉब्लम के रूप में उपस्थित है, जिसे सबसे खराब स्थिति वाले नियतात्मक समय f(n) में समाधान नहीं किया जा सकता है, लेकिन f पर निर्भर कुछ स्थिरांक के लिए इसे सबसे खराब स्थिति वाले समय af(n) में समाधान किया जा सकता है।</blockquote>
-इस प्रकार, समय सीमा में एक निरंतर-कारक वृद्धि ट्यूरिंग मशीन  की स्थिति के विपरीत, अधिक समस्याओं को हल करने की अनुमति देती है (रेखीय स्पीडअप प्रमेय देखें)। इसके अलावा, बेन-अम्राम ने साबित किया<ref>{{cite journal |last1=Ben-Amram |first1=Amir M. |title=सख्त स्थिर-कारक समय पदानुक्रम|journal=Information Processing Letters |date=2003 |volume=87 |issue=1 |pages=39-44}}</ref> उपरोक्त चालों में, बहुपद वृद्धि दर (लेकिन रैखिक से अधिक) के लिए, यह मामला है कि सभी के लिए <math>\varepsilon > 0</math>, एक निर्णय समस्या मौजूद है जिसे सबसे खराब स्थिति डिटर्मनिस्टिक समय f(n) में हल नहीं किया जा सकता है लेकिन सबसे खराब स्थिति में हल किया जा सकता है <math>(1+\varepsilon)f(n)</math>.
+इस प्रकार, समय सीमा में एक निरंतर-कारक वृद्धि ट्यूरिंग मशीन की स्थिति के विपरीत अधिक समस्याओं को समाधान करने की अनुमति देती है, रेखीय स्पीडअप प्रमेय में दर्शाया गया'है। इसके अतिरिक्त, बेन-अम्राम ने सिद्ध किया है कि<ref>{{cite journal |last1=Ben-Amram |first1=Amir M. |title=सख्त स्थिर-कारक समय पदानुक्रम|journal=Information Processing Letters |date=2003 |volume=87 |issue=1 |pages=39-44}}</ref> उपरोक्त मूवल्स में, बहुपद वृद्धि दर के लिए यह स्थिति है कि सभी के लिए <math>\varepsilon > 0</math> रैखिक से अधिक एक डिसिशन प्रॉब्लम के रूप में उपस्थित है, जिसे सबसे खराब स्थिति नियतात्मक समय f(n) में समाधान नहीं किया जा सकता है लेकिन इसे समाधान किया जा सकता है सबसे खराब स्थिति वाला समय <math>(1+\varepsilon)f(n)</math> में समाधान किया जा सकता है
 == यह भी देखें ==
-*स्थान हाइरार्की प्रमेय
+*समष्टि पदानुक्रम प्रमेय
 ==संदर्भ==
@@ Line 179: / Line 174: @@
 {{Use dmy dates|date=September 2019}}
-{{DEFAULTSORT:Time Hierarchy Theorem}}[[Category: संरचनात्मक जटिलता सिद्धांत]] [[Category: कम्प्यूटेशनल जटिलता सिद्धांत में प्रमेय]] [[Category: प्रमाण युक्त लेख]]
+{{DEFAULTSORT:Time Hierarchy Theorem}}
-[[Category: Machine Translated Page]]
+[[Category:Created On 25/07/2023|Time Hierarchy Theorem]]
-[[Category:Created On 25/07/2023]]
+[[Category:Lua-based templates|Time Hierarchy Theorem]]
+[[Category:Machine Translated Page|Time Hierarchy Theorem]]
+[[Category:Pages with script errors|Time Hierarchy Theorem]]
+[[Category:Short description with empty Wikidata description|Time Hierarchy Theorem]]
+[[Category:Templates Vigyan Ready|Time Hierarchy Theorem]]
+[[Category:Templates that add a tracking category|Time Hierarchy Theorem]]
+[[Category:Templates that generate short descriptions|Time Hierarchy Theorem]]
+[[Category:Templates using TemplateData|Time Hierarchy Theorem]]
+[[Category:Use dmy dates from September 2019|Time Hierarchy Theorem]]
+[[Category:कम्प्यूटेशनल जटिलता सिद्धांत में प्रमेय|Time Hierarchy Theorem]]
+[[Category:प्रमाण युक्त लेख|Time Hierarchy Theorem]]
+[[Category:संरचनात्मक जटिलता सिद्धांत|Time Hierarchy Theorem]]

Anonymous

Search

समय पदानुक्रम प्रमेय: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 09:53, 23 August 2023

Contents

पृष्ठभूमि

प्रमाण अवलोकन

नियतात्मक समय पदानुक्रम प्रमेय

कथन

प्रमाण

एक्सटेंशन

गैर-नियतात्मक समय पदानुक्रम प्रमेय

परिणाम

शार्पर पदानुक्रम प्रमेय

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

समय पदानुक्रम प्रमेय: Difference between revisions

Latest revision as of 09:53, 23 August 2023

पृष्ठभूमि

प्रमाण अवलोकन

नियतात्मक समय पदानुक्रम प्रमेय

कथन

प्रमाण

एक्सटेंशन

गैर-नियतात्मक समय पदानुक्रम प्रमेय

परिणाम

शार्पर पदानुक्रम प्रमेय

यह भी देखें

संदर्भ

अग्रिम पठन

Navigation

Wiki tools

Page tools

Other projects

Categories