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

कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत में, समय हाइरार्की प्रमेय ट्यूरिंग मशीनों पर समयबद्ध गणना के बारे में महत्वपूर्ण कथन हैं। और अनौपचारिक रूप से ये प्रमेय कहती है कि अधिक समय दिए जाने पर ट्यूरिंग मशीन अधिक समस्याओं का समाधान कर सकती है। उदाहरण के लिए ऐसी समस्याएं जिन्हें 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.