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

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

नियतात्मक मल्टीटेप ट्यूरिंग मशीन के लिए समय पदानुक्रम प्रमेय को पहली बार 1965 में रिचर्ड ई. स्टर्न्स और ज्यूरिस हार्टमैनिस द्वारा सिद्ध किया गया था। एक साल बाद इसमें सुधार किया गया जब एफ. सी. हेनी और रिचर्ड ई. स्टर्न्स ने यूनिवर्सल ट्यूरिंग मशीन की दक्षता में सुधार किया गया था। और इस प्रकार प्रमेय के परिणामस्वरूप प्रत्येक नियतात्मक समय-सीमाबद्ध जटिलता वर्ग के लिए स्ट्रिक्टली से बड़ा जटिल वर्ग है और इसलिए जटिलता वर्ग की समय-सीमाबद्ध में पदानुक्रम पूरी तरह से नष्ट नहीं होता है और इस प्रकार अधिक सटीक रूप से नियतात्मक ट्यूरिंग मशीन के लिए समय पदानुक्रम प्रमेय बताता है कि सभी रचनात्मक फलन के लिए समय कंस्ट्रक्टिबल फलन 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 में स्टीफन कुक द्वारा सिद्ध किया गया था। वर्ष 1978 में जोएल सेफेरस, माइकल जे. फिशर और अल्बर्ट आर. मेयर द्वारा एक जटिलता प्रमाण के माध्यम से इसके वर्तमान स्वरूप में सुधार किया गया है। और इस प्रकार विशेष रूप में वर्ष 1983 में, स्टैनिस्लाव ज़ैक ने साधारण प्रमाण के साथ वही परिणाम प्राप्त किये थे। जो गैर-नियतात्मक ट्यूरिंग मशीन के लिए समय पदानुक्रम प्रमेय बताता है कि यदि g(n) समय कंस्ट्रक्टिबल फलन f(n+1) = o(g(n)) के रूप में है,

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

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

पृष्ठभूमि

दोनों प्रमेयों एक समय कंस्ट्रक्टिबल फलन की नोशन का उपयोग करते हैं। एक फलन (गणित) $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}).$

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

$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)$ पदानुक्रम प्रमेय में बंधे निचले और ऊपरी समय के बीच प्रमाण में प्रयुक्त डिवाइस की दक्षता का पता लगाया जा सकता है, अर्थात् एक यूनिवर्सल प्रोग्राम जो चरण- सं संगणना बनाए रखता है। इसे कुछ अभिकलनात्मक मॉडलों पर अधिक कुशलता से किया जा सकता है और इस प्रकार नीचे प्रस्तुत किए गए रिणाम इसके लिए सबसे शार्पर सिद्ध हुए है।

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

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

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

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

यह भी देखें

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

अग्रिम पठन

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