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

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

गैर-डिटर्मनिस्टिक ट्यूरिंग मशीन के लिए समय हाइरार्की प्रमेय मूल रूप से 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. एल्गोरिदम का सटीक विवरण निम्न प्रकार से छोटे ओ का उपयोग करके लिखा जा सकता है: यदि एफ(एन) समय-रचना योग्य है, तो

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

उदाहरण के लिए, टाइम एनलॉग में हल करने योग्य समस्याएं हैं²n लेकिन समय और नहीं, स्थान n अंदर है

$o\left({\frac {n\log ^{2}n}{\log {(n\log ^{2}n)}}}\right).$

प्रमाण

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

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

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

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

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

हम जानते हैं कि हम एच की सदस्यता तय कर सकते हैं_fएक डिटर्मनिस्टिक ट्यूरिंग मशीन आर के माध्यम से, जो पहले एफ (| प्रत्येक चरण में, अगली कार्रवाई क्या होगी, यह तय करने के लिए सिमुलेशन मशीन को एम की परिभाषा को देखने की जरूरत है। यह कहना सुरक्षित है कि इसमें अधिकतम f(m) लगता है³ संचालन (चूंकि यह ज्ञात है कि समय कॉम्प्लेक्सिटी T(n) की मशीन का अनुकरण समय में प्राप्त किया जा सकता है $O(T(n)\cdot |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 प्रतिस्थापित करें, तो हमें वांछित परिणाम प्राप्त हो। आइए मान लें कि एच_fइस समय कॉम्प्लेक्सिटी क्लास में है, और हम एक विरोधाभास पर पहुंच जाएंगे।

यदि एच_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] (जैसा कि हम जानते हैं कि यह अधिकतम f(n) संचालन में करता है क्योंकि K, f(n) चरणों में ([N], [N]) पर रुकता है), इसका मतलब है कि K 'अस्वीकार' करता है ([N], [N]), इसलिए ([N], [N]) H में नहीं है_f, और इसी तरह एच की परिभाषा के अनुसार_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)) का एक सख्त उपसमुच्चय है।

परिणाम

समय हाइरार्की प्रमेय गारंटी देते हैं कि घातीय हाइरार्की के डिटर्मनिस्टिक और गैर-डिटर्मनिस्टिक संस्करण वास्तविक हाइरार्की हैं: दूसरे शब्दों में पी (जटिलता) ⊊ 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 DTIME(n तक संक्षिप्त नहीं होता है^k) किसी निश्चित k के लिए। उदाहरण के लिए, n में हल करने योग्य समस्याएं हैं⁵⁰⁰⁰समय लेकिन n नहीं⁴⁹⁹⁹समय. यह कोबम की थीसिस के ख़िलाफ़ एक लॉजिक्स है, यह परंपरा कि पी एल्गोरिदम का एक व्यावहारिक क्लास है। यदि ऐसा पतन होता है, तो हम यह निष्कर्ष निकाल सकते हैं कि P ≠ PSPACE, क्योंकि यह एक प्रसिद्ध प्रमेय है कि DTIME(f(n)) सख्ती से DSPACE(f(n)) में समाहित है।

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

तीव्र हाइरार्की प्रमेय

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

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

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

यदि f(n) एक समय-कंस्ट्रक्टिबल फ़ंक्शन है, तो एक निर्णय समस्या मौजूद है जिसे सबसे खराब स्थिति वाले डिटर्मनिस्टिक समय f(n) में हल नहीं किया जा सकता है, लेकिन कुछ स्थिरांक a (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.