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

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