बहुपद पदानुक्रम: Difference between revisions

From Vigyanwiki
No edit summary
 
(13 intermediate revisions by 2 users not shown)
Line 1: Line 1:
{{Short description|Computer science concept}}
{{Short description|Computer science concept}}
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल समष्टिता सिद्धांत]] में, बहुपद पदानुक्रम (कभी-कभी बहुपद-समय पदानुक्रम कहा जाता है) [[जटिलता वर्ग|समष्टिता वर्ग]]ों का [[पदानुक्रम (गणित)]] है जो वर्गों [[एनपी (जटिलता)|एनपी (समष्टिता)]] और [[सह-एनपी]] को सामान्यीकृत करता है।<ref>Arora and Barak, 2009, pp.97</ref> पदानुक्रम में प्रत्येक वर्ग [[PSPACE]] के भीतर समाहित है। पदानुक्रम को [[ओरेकल मशीन]]ों या [[वैकल्पिक ट्यूरिंग मशीन]]ों का उपयोग करके परिभाषित किया जा सकता है। यह [[गणितीय तर्क]] से [[अंकगणितीय पदानुक्रम]] और [[विश्लेषणात्मक पदानुक्रम]] का संसाधन-बद्ध समकक्ष है। पदानुक्रम में वर्गों के संघ को PH (समष्टिता) दर्शाया गया है।
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कम्प्लेक्सिटी थ्योरी]] में, '''पॉलीनोमिअल हायरार्की''' (कभी-कभी '''पॉलीनोमिअल-टाइम हायरार्की''' कहा जाता है) [[जटिलता वर्ग|कम्प्लेक्सिटी क्लासेस]] का [[पदानुक्रम (गणित)|हायरार्की]] है जो क्लासेस [[एनपी (जटिलता)|'''NP''']] और [[सह-एनपी|'''सह-NP''']] को जर्नलाइज़ करता है।<ref>Arora and Barak, 2009, pp.97</ref> हायरार्की में प्रत्येक क्लास [[PSPACE|'''पीस्पेस''']] के अंदर कॉन्टेंड है। हायरार्की को [[ओरेकल मशीन|ओरेकल मशीनों]] या [[वैकल्पिक ट्यूरिंग मशीन|अल्टरनेटिंग ट्यूरिंग मशीनों]] का उपयोग करके परिभाषित किया जा सकता है। यह [[गणितीय तर्क|मैथमेटिकल लॉजिक]] से [[अंकगणितीय पदानुक्रम|अर्थमेटिक हायरार्की]] और [[विश्लेषणात्मक पदानुक्रम|एनालिटिकल हायरार्की]] का रिसोर्स-बॉण्डेड कॉउंटरपार्ट है। हायरार्की में क्लासेस के यूनियन को '''PH''' डिनोट किया गया है।


पदानुक्रम के भीतर वर्गों में पूरी समस्याएं हैं (बहुपद-समय कटौती के संबंध में) जो पूछती हैं कि क्या मात्रात्मक बूलियन सूत्र क्वांटिफायर ऑर्डर पर प्रतिबंध वाले सूत्रों के लिए मान्य हैं। यह ज्ञात है कि समान स्तर पर या पदानुक्रम में लगातार स्तरों पर वर्गों के बीच समानता का अर्थ उस स्तर तक पदानुक्रम का पतन होगा।
हायरार्की के अंदर क्लासेस में कम्पलीट प्रॉब्लम्स हैं (पॉलीनोमिअल-टाइम रिडक्शन के संबंध में) जो पूछती हैं कि क्या मात्रात्मक बूलियन फॉर्मूले क्वांटिफायर ऑर्डर पर प्रतिबंध वाले फॉर्मूले के लिए मान्य हैं। यह ज्ञात है कि समान लेवल पर या हायरार्की में कंटिन्युअस लेवल पर क्लासेस के मध्य समानता उस लेवल तक हायरार्की के "कोलैप्स" को डिनोट करती है।


==परिभाषाएँ==
==परिभाषाएँ==
बहुपद पदानुक्रम के वर्गों की कई समकक्ष परिभाषाएँ हैं।
पॉलीनोमिअल हायरार्की के क्लासेस की कई एक्विवैलेन्ट परिभाषाएँ हैं।


===ओरेकल परिभाषा===
===ओरेकल परिभाषा===
बहुपद पदानुक्रम की दैवज्ञ परिभाषा के लिए, परिभाषित करें
पॉलीनोमिअल हायरार्की की ओरेकल परिभाषा के लिए, परिभाषित करें:


:<math>\Delta_0^\mathsf{P} := \Sigma_0^\mathsf{P} := \Pi_0^\mathsf{P} := \mathsf{P},</math>
:<math>\Delta_0^\mathsf{P} := \Sigma_0^\mathsf{P} := \Pi_0^\mathsf{P} := \mathsf{P},</math>
जहां P (समष्टिता) बहुपद समय में हल करने योग्य [[निर्णय समस्या]]ओं का समूह है। फिर i ≥ 0 के लिए परिभाषित करें
जहां P पॉलीनोमिअल टाइम में सॉल्व की जा सकने वाली [[निर्णय समस्या|डिसिशन प्रॉब्लम]] का सेट है। फिर i ≥ 0 के लिए परिभाषित करें:


:<math>\Delta_{i+1}^\mathsf{P} := \mathsf{P}^{\Sigma_i^\mathsf{P}}</math>
:<math>\Delta_{i+1}^\mathsf{P} := \mathsf{P}^{\Sigma_i^\mathsf{P}}</math>
:<math>\Sigma_{i+1}^\mathsf{P} := \mathsf{NP}^{\Sigma_i^\mathsf{P}}</math>
:<math>\Sigma_{i+1}^\mathsf{P} := \mathsf{NP}^{\Sigma_i^\mathsf{P}}</math>
:<math>\Pi_{i+1}^\mathsf{P} := \mathsf{coNP}^{\Sigma_i^\mathsf{P}}</math>
:<math>\Pi_{i+1}^\mathsf{P} := \mathsf{coNP}^{\Sigma_i^\mathsf{P}}</math>
कहाँ <math>\mathsf{P}^{\rm A}</math> कक्षा ए में कुछ पूर्ण समस्या के लिए ओरेकल मशीन द्वारा संवर्धित [[ट्यूरिंग मशीन]] द्वारा बहुपद समय में हल करने योग्य निर्णय समस्याओं का सेट है; कक्षाएं <math>\mathsf{NP}^{\rm A}</math> और <math>\mathsf{coNP}^{\rm A}</math> अनुरूप रूप से परिभाषित किए गए हैं। उदाहरण के लिए, <math> \Sigma_1^\mathsf{P} = \mathsf{NP}, \Pi_1^\mathsf{P} = \mathsf{coNP} </math>, और <math> \Delta_2^\mathsf{P} = \mathsf{P^{NP}} </math> कुछ एनपी-पूर्ण समस्या के लिए ओरेकल के साथ नियतात्मक ट्यूरिंग मशीन द्वारा बहुपद समय में हल की जाने वाली समस्याओं का वर्ग है।<ref>Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans</ref>
जहां <math>\mathsf{P}^{\rm A}</math> सेट A में किसी कम्पलीट प्रॉब्लम के लिए ओरेकल ऑगमेंटेड [[ट्यूरिंग मशीन]] द्वारा पॉलीनोमिअल टाइम में सॉल्व करने योग्य डिसिशन प्रॉब्लम का सेट है; क्लासेस <math>\mathsf{NP}^{\rm A}</math> और <math>\mathsf{coNP}^{\rm A}</math> को समान रूप से परिभाषित किया गया है। उदाहरण के लिए, <math> \Sigma_1^\mathsf{P} = \mathsf{NP}, \Pi_1^\mathsf{P} = \mathsf{coNP} </math>, और <math> \Delta_2^\mathsf{P} = \mathsf{P^{NP}} </math> कुछ NP-कम्पलीट प्रॉब्लम के लिए ओरेकल के साथ डेटर्मीनिस्टिक ट्यूरिंग मशीन द्वारा पॉलीनोमिअल टाइम में सॉल्व की जाने वाली प्रॉब्लम का क्लास है।<ref>Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans</ref>


'''मात्राबद्ध बूलियन सूत्र परिभाषा'''
'''क्वान्टीफाइड बूलियन फॉर्मूले परिभाषा'''


बहुपद पदानुक्रम की अस्तित्वगत/सार्वभौमिक परिभाषा के लिए, आइए {{mvar|L}} [[औपचारिक भाषा]] बनें (अर्थात निर्णय समस्या, {0,1} का  उपसमूह<sup>*</sup>), चलो {{mvar|p}} [[बहुपद]] बनें, और परिभाषित करें
पॉलीनोमिअल हायरार्की की एक्सिस्टेंसिअल/यूनिवर्सल परिभाषा के लिए, मान लें कि {{mvar|L}} [[औपचारिक भाषा|लैंग्वेज]] है (अर्थात डिसिशन प्रॉब्लम, {0,1}<sup>*</sup> का सबसेट), मान लीजिए कि {{mvar|p}} [[बहुपद|पॉलीनोमिअल]] है, और परिभाषित करें:


: <math> \exists^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \exists w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\}, </math>
: <math> \exists^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \exists w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\}, </math>
कहाँ <math>\langle x,w \rangle \in \{0,1\}^*</math> ल बाइनरी स्ट्रिंग के रूप में बाइनरी स्ट्रिंग्स x और w की जोड़ी की कुछ मानक एन्कोडिंग है। भाषा L स्ट्रिंग के क्रमित जोड़े के सेट का प्रतिनिधित्व करती है, जहां पहली स्ट्रिंग x इसका सदस्य है <math>\exists^p L</math>, और दूसरी स्ट्रिंग w  छोटी है (<math>|w| \leq p(|x|) </math>) गवाह गवाही दे रहा है कि x इसका सदस्य है <math>\exists^p L</math>. दूसरे शब्दों में, <math>x \in \exists^p L</math> यदि और केवल तभी जब ऐसा कोई संक्षिप्त गवाह उपस्थित हो <math> \langle x,w \rangle \in L </math>. इसी प्रकार परिभाषित करें
जहां <math>\langle x,w \rangle \in \{0,1\}^*</math> बाइनरी स्ट्रिंग्स x और w के पेअर सिंगल बाइनरी स्ट्रिंग के रूप में कुछ स्टैण्डर्ड एन्कोडिंग है। लैंग्वेज L स्ट्रिंग के क्रमित पेअर के सेट को रिप्रेजेंट करती है, जहां प्रथम स्ट्रिंग x, <math>\exists^p L</math> का मेंबर है, और दूसरी स्ट्रिंग w  छोटी है (<math>|w| \leq p(|x|) </math>) डायरेक्ट रिजल्ट दे रहा है कि x, <math>\exists^p L</math> का मेंबर है। दूसरे शब्दों में, <math>x \in \exists^p L</math> यदि और केवल तभी जब ऐसा कोई शार्ट टेस्टिफाइंग उपस्थित हो, जैसे कि <math> \langle x,w \rangle \in L </math> है। इसी प्रकार परिभाषित करें:


: <math> \forall^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \forall w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\} </math>
: <math> \forall^p L := \left\{ x \in \{0,1\}^* \ \left| \ \left( \forall w \in \{0,1\}^{\leq p(|x|)} \right) \langle x,w \rangle \in L \right. \right\} </math>
ध्यान दें कि डी मॉर्गन के कानून मानते हैं: <math> \left( \exists^p L \right)^{\rm c} = \forall^p L^{\rm c} </math> और <math> \left( \forall^p L \right)^{\rm c} = \exists^p L^{\rm c} </math>, जहां एल<sup>c</sup>L का पूरक है।
ध्यान दें कि डी मॉर्गन का नियम मानता है: <math> \left( \exists^p L \right)^{\rm c} = \forall^p L^{\rm c} </math> और <math> \left( \forall^p L \right)^{\rm c} = \exists^p L^{\rm c} </math> है, जहां L<sup>c</sup> L का कॉम्प्लीमेंट है।


होने देना {{mathcal|C}} भाषाओं का वर्ग बनें। परिभाषा के अनुसार इन ऑपरेटरों को भाषाओं की संपूर्ण कक्षाओं पर काम करने के लिए विस्तारित करें
मान लीजिए {{mathcal|C}} लैंग्वेज का क्लास है। परिभाषा के अनुसार इन ऑपरेटरों को लैंग्वेज की होल क्लासेस पर वर्क करने के लिए विस्तारित किया जाता है:


:<math>\exists^\mathsf{P} \mathcal{C} := \left\{\exists^p L \ | \ p \text{ is a polynomial and } L \in \mathcal{C} \right\}</math>
:<math>\exists^\mathsf{P} \mathcal{C} := \left\{\exists^p L \ | \ p \text{ is a polynomial and } L \in \mathcal{C} \right\}</math>
:<math>\forall^\mathsf{P} \mathcal{C} := \left\{\forall^p L \ | \ p \text{ is a polynomial and } L \in \mathcal{C} \right\}</math>
:<math>\forall^\mathsf{P} \mathcal{C} := \left\{\forall^p L \ | \ p \text{ is a polynomial and } L \in \mathcal{C} \right\}</math>
फिर से, डी मॉर्गन के कानून कायम हैं: <math> \mathsf{co} \exists^\mathsf{P} \mathcal{C} = \forall^\mathsf{P} \mathsf{co} \mathcal{C} </math> और <math> \mathsf{co} \forall^\mathsf{P} \mathcal{C} = \exists^\mathsf{P} \mathsf{co} \mathcal{C} </math>, कहाँ <math>\mathsf{co}\mathcal{C} = \left\{ L^c | L \in \mathcal{C} \right\}</math>.
पुनः, डी मॉर्गन का नियम कांस्टेंट हैं: <math> \mathsf{co} \exists^\mathsf{P} \mathcal{C} = \forall^\mathsf{P} \mathsf{co} \mathcal{C} </math> और <math> \mathsf{co} \forall^\mathsf{P} \mathcal{C} = \exists^\mathsf{P} \mathsf{co} \mathcal{C} </math>, जहां <math>\mathsf{co}\mathcal{C} = \left\{ L^c | L \in \mathcal{C} \right\}</math> है।


वर्ग एनपी (समष्टिता) और सह-एनपी को इस प्रकार परिभाषित किया जा सकता है <math> \mathsf{NP} = \exists^\mathsf{P} \mathsf{P} </math>, और <math> \mathsf{coNP} = \forall^\mathsf{P} \mathsf{P} </math>, जहां पी (समष्टिता) सभी व्यवहार्य (बहुपद-समय) निर्णय योग्य भाषाओं का वर्ग है। बहुपद पदानुक्रम को पुनरावर्ती रूप से परिभाषित किया जा सकता है
'''NP''' और '''co-NP''' को इस प्रकार <math> \mathsf{NP} = \exists^\mathsf{P} \mathsf{P} </math>, और <math> \mathsf{coNP} = \forall^\mathsf{P} \mathsf{P} </math> परिभाषित किया जा सकता है, जहां '''P''' सभी संभावित (पॉलीनोमिअल-टाइम) डिसिशन योग्य लैंग्वेज का क्लास है। पॉलीनोमिअल हायरार्की को रेकर्सिवली रूप से परिभाषित किया जा सकता है:


:<math> \Sigma_0^\mathsf{P} := \Pi_0^\mathsf{P} := \mathsf{P} </math>
:<math> \Sigma_0^\mathsf{P} := \Pi_0^\mathsf{P} := \mathsf{P} </math>
:<math> \Sigma_{k+1}^\mathsf{P} := \exists^\mathsf{P} \Pi_k^\mathsf{P} </math>
:<math> \Sigma_{k+1}^\mathsf{P} := \exists^\mathsf{P} \Pi_k^\mathsf{P} </math>
:<math> \Pi_{k+1}^\mathsf{P} := \forall^\mathsf{P} \Sigma_k^\mathsf{P} </math>
:<math> \Pi_{k+1}^\mathsf{P} := \forall^\mathsf{P} \Sigma_k^\mathsf{P} </math>
ध्यान दें कि <math> \mathsf{NP} = \Sigma_1^\mathsf{P} </math>, और <math> \mathsf{coNP} = \Pi_1^\mathsf{P} </math>.
ध्यान दें कि <math> \mathsf{NP} = \Sigma_1^\mathsf{P} </math>, और <math> \mathsf{coNP} = \Pi_1^\mathsf{P} </math> है।


यह परिभाषा बहुपद पदानुक्रम और अंकगणितीय पदानुक्रम के बीच घनिष्ठ संबंध को दर्शाती है, जहां निर्णायक भाषा और पुनरावर्ती गणना योग्य भाषा क्रमशः पी (समष्टिता) और एनपी (समष्टिता) के अनुरूप भूमिका निभाती है। [[बेयर स्पेस (सेट सिद्धांत)]] के सबसेट का पदानुक्रम देने के लिए [[विश्लेषणात्मक पदानुक्रम]] को भी इसी तरह से परिभाषित किया गया है।
यह परिभाषा पॉलीनोमिअल हायरार्की और अर्थमेटिक हायरार्की के मध्य घनिष्ठ संबंध को दर्शाती है, जहां निर्णायक लैंग्वेज और रेकर्सिवली कैलक्यूलेशन योग्य लैंग्वेज क्रमशः P और NP के अनुरूप भूमिका निभाते है। [[बेयर स्पेस (सेट सिद्धांत)|रियल नंबर्स]] के सबसेट का हायरार्की देने के लिए [[विश्लेषणात्मक पदानुक्रम|एनालिटिक हायरार्की]] को भी इसी प्रकार से परिभाषित किया गया है।


===वैकल्पिक ट्यूरिंग मशीनों की परिभाषा===
===अल्टरनेटिंग ट्यूरिंग मशीनों की परिभाषा===
वैकल्पिक ट्यूरिंग मशीन गैर-नियतात्मक ट्यूरिंग मशीन है जिसमें गैर-अंतिम अवस्थाएँ अस्तित्वगत और सार्वभौमिक अवस्थाओं में विभाजित होती हैं। यह अंततः अपने वर्तमान कॉन्फ़िगरेशन से स्वीकार कर रहा है यदि: यह अस्तित्वगत स्थिति में है और कुछ अंततः स्वीकार्य कॉन्फ़िगरेशन में परिवर्तित हो सकता है; या, यह सार्वभौमिक स्थिति में है और प्रत्येक संक्रमण अंततः कुछ स्वीकार्य विन्यास में होता है; या, यह स्वीकार्य स्थिति में है।<ref>Arora and Barak, pp.99–100</ref>
अल्टरनेटिंग ट्यूरिंग मशीन गैर-नियतात्मक ट्यूरिंग मशीन है जिसमें नॉन-फाइनल स्टेट एक्सिस्टेंसिअल और यूनिवर्सल स्टेट में डिवाइड होती हैं। यह अंततः अपने वर्तमान कॉन्फ़िगरेशन से एक्सेप्टिंग कर रहा है यदि: यह एक्सिस्टेंसिअल स्टेट में है और कुछ अंततः स्वीकार्य कॉन्फ़िगरेशन में परिवर्तित हो सकता है; या, यह यूनिवर्सल स्टेट में है और प्रत्येक संक्रमण अंततः कुछ स्वीकार्य विन्यास में होता है; या, यह एक्सेप्टिंग स्टेट में है।<ref>Arora and Barak, pp.99–100</ref>
हम परिभाषित करते हैं <math>\Sigma_k^\mathsf{P}</math> बहुपद समय में  वैकल्पिक ट्यूरिंग मशीन द्वारा स्वीकृत भाषाओं का वर्ग होना जैसे कि प्रारंभिक स्थिति  अस्तित्वगत स्थिति है और प्रत्येक पथ मशीन अस्तित्वगत और सार्वभौमिक राज्यों के बीच अधिकतम k - 1 बार स्वैप ले सकती है। हम परिभाषित करते हैं <math>\Pi_k^\mathsf{P}</math> इसी प्रकार, सिवाय इसके कि प्रारंभिक अवस्था  सार्वभौमिक अवस्था है।<ref>Arora and Barak, pp.100</ref>
यदि हम अस्तित्वगत और सार्वभौमिक अवस्थाओं के बीच अधिकतम k-1 स्वैप की आवश्यकता को छोड़ देते हैं, ताकि हमें केवल यह आवश्यक हो कि हमारी वैकल्पिक ट्यूरिंग मशीन बहुपद समय में चले, तो हमारे पास वर्ग 'एपी' की परिभाषा है, जो 'पीएसपीएसीई' के बराबर है।<ref>Arora and Barak, pp.100</ref>


== बहुपद पदानुक्रम में वर्गों के बीच संबंध ==
हम <math>\Sigma_k^\mathsf{P}</math> परिभाषित करते हैं पॉलीनोमिअल टाइम में अल्टरनेटिंग ट्यूरिंग मशीन द्वारा एक्सेप्टिंग लैंग्वेज का क्लास होने के लिए जैसे कि प्रारंभिक स्टेट एक्सिस्टेंसिअल स्टेट है और प्रत्येक एड्रेस मशीन एक्सिस्टेंसिअल और यूनिवर्सल स्टेट के मध्य अधिकतम k - 1 बार स्वैप ले सकती है। हम परिभाषित करते हैं <math>\Pi_k^\mathsf{P}</math> इसी प्रकार, अतिरिक्त इसके कि प्रारंभिक स्टेट यूनिवर्सल स्टेट है।<ref>Arora and Barak, pp.100</ref>
[[Image:Polynomial time hierarchy.svg|250px|thumb|right|बहुपद समय पदानुक्रम के समतुल्य क्रमविनिमेय आरेख। तीर समावेशन को दर्शाते हैं।]]बहुपद पदानुक्रम में सभी वर्गों का मिलन समष्टिता वर्ग PH (समष्टिता) है।


परिभाषाएँ संबंधों का संकेत देती हैं:
यदि हम एक्सिस्टेंसिअल और यूनिवर्सल स्टेट के मध्य अधिकतम k-1 स्वैप की आवश्यकता को ओमिट कर देते हैं, जिससे कि हमें केवल यह आवश्यक हो कि हमारी अल्टरनेटिंग ट्यूरिंग मशीन पॉलीनोमिअल टाइम में चले, तो हमारे पास क्लास '<nowiki/>'''एपी'''<nowiki/>' की परिभाषा है, जो ''''पीस्पेस'''<nowiki/>' के समान है।<ref>Arora and Barak, pp.100</ref>
 
== पॉलीनोमिअल हायरार्की में क्लासेस के मध्य संबंध ==
[[Image:Polynomial time hierarchy.svg|250px|thumb|right|पॉलीनोमिअल टाइम हायरार्की के एक्विवैलेन्ट कम्यूटेटिव डायग्राम। एरो इन्क्लुज़न को दर्शाते हैं।]]पॉलीनोमिअल हायरार्की में सभी क्लासेस का मिलन कम्प्लेक्सिटी क्लास '''PH''' है।
 
परिभाषाएँ संबंधों का सिग्नल देती हैं:


:<math>\Sigma_i^\mathsf{P} \subseteq \Delta_{i+1}^\mathsf{P} \subseteq \Sigma_{i+1}^\mathsf{P}</math>
:<math>\Sigma_i^\mathsf{P} \subseteq \Delta_{i+1}^\mathsf{P} \subseteq \Sigma_{i+1}^\mathsf{P}</math>
:<math>\Pi_i^\mathsf{P} \subseteq \Delta_{i+1}^\mathsf{P} \subseteq \Pi_{i+1}^\mathsf{P}</math>
:<math>\Pi_i^\mathsf{P} \subseteq \Delta_{i+1}^\mathsf{P} \subseteq \Pi_{i+1}^\mathsf{P}</math>
:<math>\Sigma_i^\mathsf{P} = \mathsf{co}\Pi_{i}^\mathsf{P}</math>
:<math>\Sigma_i^\mathsf{P} = \mathsf{co}\Pi_{i}^\mathsf{P}</math>
अंकगणितीय और विश्लेषणात्मक पदानुक्रमों के विपरीत, जिनके समावेशन को उचित माना जाता है, यह खुला प्रश्न है कि क्या इनमें से कोई भी समावेशन उचित है, हालांकि यह व्यापक रूप से माना जाता है कि वे सभी हैं। यदि कोई <math>\Sigma_k^\mathsf{P} = \Sigma_{k+1}^\mathsf{P}</math>, या यदि कोई हो <math>\Sigma_k^\mathsf{P} = \Pi_{k}^\mathsf{P}</math>, फिर पदानुक्रम सभी के लिए स्तर k: तक ढह जाता है <math>i > k</math>, <math>\Sigma_i^\mathsf{P} = \Sigma_k^\mathsf{P}</math>.<ref>Arora and Barak, 2009, Theorem 5.4</ref> विशेष रूप से, हमारे पास अनसुलझी समस्याओं से जुड़े निम्नलिखित निहितार्थ हैं:
अर्थमेटिक और एनालिटिक हायरार्की के विपरीत, जिनके इन्क्लूज़न को उचित माना जाता है, यह ओपन प्रश्न है कि क्या इनमें से कोई भी इन्क्लूज़न उचित है, चूँकि यह व्यापक रूप से माना जाता है कि वे सभी हैं। यदि कोई <math>\Sigma_k^\mathsf{P} = \Sigma_{k+1}^\mathsf{P}</math>, या यदि कोई <math>\Sigma_k^\mathsf{P} = \Pi_{k}^\mathsf{P}</math> है, तब हायरार्की सभी के लिए लेवल k: तक आवश्यक हो जाता है <math>i > k</math>, <math>\Sigma_i^\mathsf{P} = \Sigma_k^\mathsf{P}</math>है।<ref>Arora and Barak, 2009, Theorem 5.4</ref> विशेष रूप से, हमारे पास अनसाल्व्ड प्रॉब्लम से जुड़े निम्नलिखित इम्प्लिकेशन्स हैं:


* पी बनाम एनपी समस्या|पी = एनपी यदि और केवल यदि पी = पीएच।<ref>{{cite book|title=असतत और संयुक्त गणित की पुस्तिका|series=Discrete Mathematics and Its Applications|editor-first=Kenneth H.|editor-last=Rosen|edition=2nd|publisher=CRC Press|year=2018|pages=1308–1314|isbn=9781351644051|chapter=17.5 Complexity classes|first=Lane|last=Hemaspaandra}}</ref>
* '''P''' = '''NP''' यदि और केवल '''P''' = '''PH''' है।<ref>{{cite book|title=असतत और संयुक्त गणित की पुस्तिका|series=Discrete Mathematics and Its Applications|editor-first=Kenneth H.|editor-last=Rosen|edition=2nd|publisher=CRC Press|year=2018|pages=1308–1314|isbn=9781351644051|chapter=17.5 Complexity classes|first=Lane|last=Hemaspaandra}}</ref>
* यदि एनपी = सह-एनपी तो एनपी = पीएच। (सह-एनपी है <math>\Pi_1^\mathsf{P}</math>.)
* यदि '''NP''' = '''co-NP''' तो '''NP''' = '''PH''' है। ('''co-NP''' <math>\Pi_1^\mathsf{P}</math>है)
वह मामला जिसमें एनपी = पीएच को पीएच के ''दूसरे स्तर'' तक ''पतन'' भी कहा जाता है। मामला P = NP, PH से P के पतन से मेल खाता है।
वह स्टेट जिसमें '''NP''' = '''PH''' को '''PH''' के दूसरे लेवल तक कोलैप्स भी कहा जाता है। स्टेट P = NP, PH से P के कोलैप्स से युग्मित होता है।


{{Unsolved|computer science|{{tmath|1= \mathsf{P} \overset{?}{=} \mathsf{NP} }}}}
{{Unsolved|computer science|{{tmath|1= \mathsf{P} \overset{?}{=} \mathsf{NP} }}}}


पहले स्तर तक पतन का प्रश्न सामान्यतः बेहद कठिन माना जाता है। अधिकांश शोधकर्ता दूसरे स्तर तक भी पतन में विश्वास नहीं करते हैं।
प्रथम लेवल तक कोलैप्स का प्रश्न सामान्यतः अधिक कठिन माना जाता है। अधिकांश शोधकर्ता दूसरे लेवल तक भी कोलैप्स में विश्वास नहीं करते हैं।


== अन्य वर्गों से संबंध ==
== अन्य क्लासेस से संबंध ==
{{See also|पीएच (समष्टिता) अन्य वर्गों से संबंध}}
{{See also|पीएच (समष्टिता) अन्य वर्गों से संबंध}}
{{unsolved|computer science|{{tmath|1= \mathsf{PH} \overset{?}{=} \mathsf{PSPACE} }}}}
{{unsolved|computer science|{{tmath|1= \mathsf{PH} \overset{?}{=} \mathsf{PSPACE} }}}}


[[File:Complexity-classes-polynomial.svg|thumb|पी (समष्टिता), एनपी (समष्टिता), सह-एनपी, [[बीपीपी (जटिलता)|बीपीपी (समष्टिता)]], पी/पॉली, पीएच (समष्टिता), और पीएसपीएसीई सहित समष्टिता वर्गों का हैस आरेख]]बहुपद पदानुक्रम [[घातीय पदानुक्रम]] और अंकगणितीय पदानुक्रम का एनालॉग (बहुत कम समष्टिता पर) है।
[[File:Complexity-classes-polynomial.svg|thumb|P, NP, co-NP, [[बीपीपी (जटिलता)|BPP]], P/poly, PH, और पीएसपीएसीई सहित कम्प्लेक्सिटी क्लासेस का हैस आरेख है।]]पॉलीनोमिअल हायरार्की [[घातीय पदानुक्रम|एक्सपोनेंशियल हायरार्की]] और अर्थमेटिक हायरार्की का एनालॉग (अधिक लोअर कम्प्लेक्सिटी पर) है।
 
यह ज्ञात है कि PH पीस्पेस के अंदर कॉन्टेंड है, किन्तु यह ज्ञात नहीं है कि दोनों क्लास समान हैं या नहीं हैं। इस प्रॉब्लम का उपयोगी सुधार यह है कि PH = पीस्पेस यदि और केवल परिमित संरचनाओं पर दूसरे क्रम के लॉजिक को[[ सकर्मक समापन |ट्रान्सिटीव क्लोज़र]] ऑपरेटर के अतिरिक्त कोई शक्ति नहीं मिलती है।


यह ज्ञात है कि PH PSPACE के भीतर समाहित है, लेकिन यह ज्ञात नहीं है कि दोनों वर्ग समान हैं या नहीं। इस समस्या का  उपयोगी सुधार यह है कि PH = PSPACE यदि और केवल यदि SO (समष्टिता) | परिमित संरचनाओं पर दूसरे क्रम के तर्क को [[ सकर्मक समापन ]] ऑपरेटर के अतिरिक्त कोई अतिरिक्त शक्ति नहीं मिलती है।
यदि पॉलीनोमिअल हायरार्की में कोई कम्पलीट प्रॉब्लम है, तो इसमें केवल लिमिटेड रूप से कई भिन्न-भिन्न लेवल हैं। चूंकि पीएसपीएसीई-कम्पलीट प्रॉब्लम्स हैं, हम जानते हैं कि यदि पीएसपीएसीई = PH, तो पॉलीनोमिअल हायरार्की अवश्य होना चाहिए, क्योंकि पीएसपीएसीई-कम्पलीट प्रॉब्लम होगी <math>\Sigma_{k}^\mathsf{P}</math>-कुछ k के लिए कम्पलीट प्रॉब्लम है।<ref>Arora and Barak, 2009, Claim 5.5</ref>


यदि बहुपद पदानुक्रम में कोई पूर्ण समस्या है, तो इसमें केवल सीमित रूप से कई अलग-अलग स्तर हैं। चूंकि पीएसपीएसीई-पूर्ण समस्याएं हैं, हम जानते हैं कि यदि पीएसपीएसीई = पीएच, तो बहुपद पदानुक्रम ढह जाना चाहिए, क्योंकि पीएसपीएसीई-पूर्ण समस्या  होगी <math>\Sigma_{k}^\mathsf{P}</math>-कुछ के लिए पूरी समस्या।<ref>Arora and Barak, 2009, Claim 5.5</ref>
पॉलीनोमिअल हायरार्की में प्रत्येक क्लास में सम्मिलित हैं <math>\leq_{\rm m}^\mathsf{P}</math>-कम्पलीट प्रॉब्लम्स (पॉलीनोमिअल-टाइम अनेक-रिडक्शन के अंतर्गत कम्पलीट प्रॉब्लम्स) हैं। इसके अतिरिक्त, पॉलीनोमिअल हायरार्की में प्रत्येक क्लास के अंतर्गत विवृत <math>\leq_{\rm m}^\mathsf{P}</math>-कटौती है: जिसका अर्थ है कि हायरार्की में क्लास {{mathcal|C}} और लैंग्वेज <math>L \in \mathcal{C}</math> के लिए, यदि <math>A \leq_{\rm m}^\mathsf{P} L</math>, तब <math>A \in \mathcal{C}</math> होता है। ये दोनों तथ्य मिलकर यह दर्शाते हैं कि यदि <math>K_i</math> के लिए कम्पलीट प्रॉब्लम <math>\Sigma_{i}^\mathsf{P}</math>, तब <math>\Sigma_{i+1}^\mathsf{P} = \mathsf{NP}^{K_i}</math>, और <math>\Pi_{i+1}^\mathsf{P} = \mathsf{coNP}^{K_i}</math> है। उदाहरण के लिए, <math>\Sigma_{2}^\mathsf{P} = \mathsf{NP}^\mathsf{SAT}</math>है। दूसरे शब्दों में, यदि किसी लैंग्वेज को {{mathcal|C}} में किसी ओरेकल के आधार पर परिभाषित किया जाता है, तो हम मान सकते हैं कि इसे {{mathcal|C}} के लिए कम्पलीट प्रॉब्लम के आधार पर परिभाषित किया जाता है। इसलिए कम्पलीट प्रॉब्लम्स उस क्लास के रिप्रेजेन्टेटिव के रूप में वर्क करती हैं जिसके लिए वे कम्पलीट हैं।
बहुपद पदानुक्रम में प्रत्येक वर्ग में सम्मिलित हैं <math>\leq_{\rm m}^\mathsf{P}</math>-पूर्ण समस्याएँ (बहुपद-समय अनेक- कटौती के अंतर्गत पूर्ण समस्याएँ)। इसके अतिरिक्त, बहुपद पदानुक्रम में प्रत्येक वर्ग के अंतर्गत बंद है <math>\leq_{\rm m}^\mathsf{P}</math>-कटौती: जिसका अर्थ है कि वर्ग के लिए {{mathcal|C}} पदानुक्रम और भाषा में <math>L \in \mathcal{C}</math>, अगर <math>A \leq_{\rm m}^\mathsf{P} L</math>, तब <math>A \in \mathcal{C}</math> भी। ये दोनों तथ्य मिलकर यह दर्शाते हैं कि यदि <math>K_i</math> के लिए पूरी समस्या है <math>\Sigma_{i}^\mathsf{P}</math>, तब <math>\Sigma_{i+1}^\mathsf{P} = \mathsf{NP}^{K_i}</math>, और <math>\Pi_{i+1}^\mathsf{P} = \mathsf{coNP}^{K_i}</math>. उदाहरण के लिए, <math>\Sigma_{2}^\mathsf{P} = \mathsf{NP}^\mathsf{SAT}</math>. दूसरे शब्दों में, यदि किसी भाषा को किसी दैवज्ञ के आधार पर परिभाषित किया जाता है {{mathcal|C}}, तो हम मान सकते हैं कि इसे संपूर्ण समस्या के आधार पर परिभाषित किया गया है {{mathcal|C}}. इसलिए पूर्ण समस्याएँ उस वर्ग के प्रतिनिधि के रूप में कार्य करती हैं जिसके लिए वे पूर्ण हैं।


सिप्सर-लॉटमैन प्रमेय में कहा गया है कि वर्ग बाउंडेड-त्रुटि संभाव्य बहुपद बहुपद पदानुक्रम के दूसरे स्तर में निहित है।
सिप्सर-लॉटमैन प्रमेय में कहा गया है कि क्लास बीपीपी पॉलीनोमिअल हायरार्की के दूसरे लेवल में कॉन्टेंड है।


कार्प-लिप्टन प्रमेय|कन्नन के प्रमेय में कहा गया है कि किसी भी k के लिए, <math>\Sigma_2</math> SIZE(n) में सम्मिलित नहीं है<sup>क</sup>).
कन्नन के प्रमेय में कहा गया है कि किसी भी k के लिए, <math>\Sigma_2</math> SIZE(n<sup>k</sup>) में सम्मिलित नहीं है।


टोडा के प्रमेय में कहा गया है कि बहुपद पदानुक्रम पी में निहित है<sup>#पी</sup>.
टोडा के प्रमेय में कहा गया है कि पॉलीनोमिअल हायरार्की P<sup>#P</sup> में कॉन्टेंड है।


==समस्याएँ==
==प्रॉब्लम्स==
{{unordered list
{{unordered list
|1=
|1=
Line 121: Line 124:


== यह भी देखें ==
== यह भी देखें ==
*[[एक्सटाइम|्सटाइम]]
*[[एक्सटाइम]]
*घातांकीय पदानुक्रम
*घातांकीय हायरार्की
* [[अंकगणितीय पदानुक्रम]]
* [[अंकगणितीय पदानुक्रम|अर्थमेटिक हायरार्की]]


==संदर्भ==
==संदर्भ==
Line 129: Line 132:
'''सामान्य सन्दर्भ'''
'''सामान्य सन्दर्भ'''
# {{cite book |last1= Arora |first1= Sanjeev |last2= Barak |first2= Boaz |url= http://www.cs.princeton.edu/theory/complexity/ |title= जटिलता सिद्धांत: एक आधुनिक दृष्टिकोण|publisher= Cambridge University Press |date= 2009 |isbn= 978-0-521-42426-4 |quote= खंड 1.4, "स्ट्रिंग्स के रूप में मशीनें और सार्वभौमिक ट्यूरिंग मशीन" और 1.7, "प्रमेय का प्रमाण 1.9"}}
# {{cite book |last1= Arora |first1= Sanjeev |last2= Barak |first2= Boaz |url= http://www.cs.princeton.edu/theory/complexity/ |title= जटिलता सिद्धांत: एक आधुनिक दृष्टिकोण|publisher= Cambridge University Press |date= 2009 |isbn= 978-0-521-42426-4 |quote= खंड 1.4, "स्ट्रिंग्स के रूप में मशीनें और सार्वभौमिक ट्यूरिंग मशीन" और 1.7, "प्रमेय का प्रमाण 1.9"}}
# अल्बर्ट आर. मेयर|ए. आर. मेयर और लैरी स्टॉकमेयर|एल. जे. स्टॉकमेयर. वर्ग के साथ नियमित अभिव्यक्तियों के लिए समतुल्यता समस्या के लिए घातांकीय स्थान की आवश्यकता होती है। स्विचिंग और ऑटोमेटा थ्योरी पर 13वीं आईईईई संगोष्ठी की कार्यवाही में, पृष्ठ 125-129, 1972। वह पेपर जिसने बहुपद पदानुक्रम का परिचय दिया।
# अल्बर्ट आर. मेयर|ए. आर. मेयर और लैरी स्टॉकमेयर|एल. जे. स्टॉकमेयर. क्लास के साथ नियमित अभिव्यक्तियों के लिए समतुल्यता प्रॉब्लम के लिए घातांकीय स्थान की आवश्यकता होती है। स्विचिंग और ऑटोमेटा थ्योरी पर 13वीं आईईईई संगोष्ठी की कार्यवाही में, पृष्ठ 125-129, 1972। वह पेपर जिसने पॉलीनोमिअल हायरार्की का परिचय दिया।
# लैरी स्टॉकमेयर|एल. जे. स्टॉकमेयर. :doi:10.1016/0304-3975(76)90061-X|बहुपद-समय पदानुक्रम। सैद्धांतिक कंप्यूटर विज्ञान, खंड 3, पृष्ठ 1-22, 1976।
# लैरी स्टॉकमेयर|एल. जे. स्टॉकमेयर. :doi:10.1016/0304-3975(76)90061-X|पॉलीनोमिअल-टाइम हायरार्की। सैद्धांतिक कंप्यूटर विज्ञान, खंड 3, पृष्ठ 1-22, 1976।
# क्रिस्टोस पापादिमित्रीउ|सी. पापादिमित्रीउ. अभिकलनात्मक समष्टिता। एडिसन-वेस्ले, 1994। अध्याय 17. बहुपद पदानुक्रम, पीपी. 409-438।
# क्रिस्टोस पापादिमित्रीउ|सी. पापादिमित्रीउ. अभिकलनात्मक कम्प्लेक्सिटी। एडिसन-वेस्ले, 1994। अध्याय 17. पॉलीनोमिअल हायरार्की, पीपी. 409-438।
# {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[कंप्यूटर और इंट्रेक्टेबिलिटी: एनपी-पूर्णता के सिद्धांत के लिए एक गाइड]]| publisher = W.H. Freeman | isbn = 0-7167-1045-5}} धारा 7.2: बहुपद पदानुक्रम, पृष्ठ 161-167।
# {{cite book|author = [[Michael R. Garey]] and [[David S. Johnson]] | year = 1979 | title = [[कंप्यूटर और इंट्रेक्टेबिलिटी: एनपी-पूर्णता के सिद्धांत के लिए एक गाइड]]| publisher = W.H. Freeman | isbn = 0-7167-1045-5}} धारा 7.2: पॉलीनोमिअल हायरार्की, पृष्ठ 161-167।


===उद्धरण===
===उद्धरण===
Line 144: Line 147:
[[Category: Machine Translated Page]]
[[Category: Machine Translated Page]]
[[Category:Created On 25/07/2023]]
[[Category:Created On 25/07/2023]]
[[Category:Vigyan Ready]]

Latest revision as of 22:26, 2 February 2024

कम्प्यूटेशनल कम्प्लेक्सिटी थ्योरी में, पॉलीनोमिअल हायरार्की (कभी-कभी पॉलीनोमिअल-टाइम हायरार्की कहा जाता है) कम्प्लेक्सिटी क्लासेस का हायरार्की है जो क्लासेस NP और सह-NP को जर्नलाइज़ करता है।[1] हायरार्की में प्रत्येक क्लास पीस्पेस के अंदर कॉन्टेंड है। हायरार्की को ओरेकल मशीनों या अल्टरनेटिंग ट्यूरिंग मशीनों का उपयोग करके परिभाषित किया जा सकता है। यह मैथमेटिकल लॉजिक से अर्थमेटिक हायरार्की और एनालिटिकल हायरार्की का रिसोर्स-बॉण्डेड कॉउंटरपार्ट है। हायरार्की में क्लासेस के यूनियन को PH डिनोट किया गया है।

हायरार्की के अंदर क्लासेस में कम्पलीट प्रॉब्लम्स हैं (पॉलीनोमिअल-टाइम रिडक्शन के संबंध में) जो पूछती हैं कि क्या मात्रात्मक बूलियन फॉर्मूले क्वांटिफायर ऑर्डर पर प्रतिबंध वाले फॉर्मूले के लिए मान्य हैं। यह ज्ञात है कि समान लेवल पर या हायरार्की में कंटिन्युअस लेवल पर क्लासेस के मध्य समानता उस लेवल तक हायरार्की के "कोलैप्स" को डिनोट करती है।

परिभाषाएँ

पॉलीनोमिअल हायरार्की के क्लासेस की कई एक्विवैलेन्ट परिभाषाएँ हैं।

ओरेकल परिभाषा

पॉलीनोमिअल हायरार्की की ओरेकल परिभाषा के लिए, परिभाषित करें:

जहां P पॉलीनोमिअल टाइम में सॉल्व की जा सकने वाली डिसिशन प्रॉब्लम का सेट है। फिर i ≥ 0 के लिए परिभाषित करें:

जहां सेट A में किसी कम्पलीट प्रॉब्लम के लिए ओरेकल ऑगमेंटेड ट्यूरिंग मशीन द्वारा पॉलीनोमिअल टाइम में सॉल्व करने योग्य डिसिशन प्रॉब्लम का सेट है; क्लासेस और को समान रूप से परिभाषित किया गया है। उदाहरण के लिए, , और कुछ NP-कम्पलीट प्रॉब्लम के लिए ओरेकल के साथ डेटर्मीनिस्टिक ट्यूरिंग मशीन द्वारा पॉलीनोमिअल टाइम में सॉल्व की जाने वाली प्रॉब्लम का क्लास है।[2]

क्वान्टीफाइड बूलियन फॉर्मूले परिभाषा

पॉलीनोमिअल हायरार्की की एक्सिस्टेंसिअल/यूनिवर्सल परिभाषा के लिए, मान लें कि L लैंग्वेज है (अर्थात डिसिशन प्रॉब्लम, {0,1}* का सबसेट), मान लीजिए कि p पॉलीनोमिअल है, और परिभाषित करें:

जहां बाइनरी स्ट्रिंग्स x और w के पेअर सिंगल बाइनरी स्ट्रिंग के रूप में कुछ स्टैण्डर्ड एन्कोडिंग है। लैंग्वेज L स्ट्रिंग के क्रमित पेअर के सेट को रिप्रेजेंट करती है, जहां प्रथम स्ट्रिंग x, का मेंबर है, और दूसरी स्ट्रिंग w छोटी है () डायरेक्ट रिजल्ट दे रहा है कि x, का मेंबर है। दूसरे शब्दों में, यदि और केवल तभी जब ऐसा कोई शार्ट टेस्टिफाइंग उपस्थित हो, जैसे कि है। इसी प्रकार परिभाषित करें:

ध्यान दें कि डी मॉर्गन का नियम मानता है: और है, जहां Lc L का कॉम्प्लीमेंट है।

मान लीजिए C लैंग्वेज का क्लास है। परिभाषा के अनुसार इन ऑपरेटरों को लैंग्वेज की होल क्लासेस पर वर्क करने के लिए विस्तारित किया जाता है:

पुनः, डी मॉर्गन का नियम कांस्टेंट हैं: और , जहां है।

NP और co-NP को इस प्रकार , और परिभाषित किया जा सकता है, जहां P सभी संभावित (पॉलीनोमिअल-टाइम) डिसिशन योग्य लैंग्वेज का क्लास है। पॉलीनोमिअल हायरार्की को रेकर्सिवली रूप से परिभाषित किया जा सकता है:

ध्यान दें कि , और है।

यह परिभाषा पॉलीनोमिअल हायरार्की और अर्थमेटिक हायरार्की के मध्य घनिष्ठ संबंध को दर्शाती है, जहां निर्णायक लैंग्वेज और रेकर्सिवली कैलक्यूलेशन योग्य लैंग्वेज क्रमशः P और NP के अनुरूप भूमिका निभाते है। रियल नंबर्स के सबसेट का हायरार्की देने के लिए एनालिटिक हायरार्की को भी इसी प्रकार से परिभाषित किया गया है।

अल्टरनेटिंग ट्यूरिंग मशीनों की परिभाषा

अल्टरनेटिंग ट्यूरिंग मशीन गैर-नियतात्मक ट्यूरिंग मशीन है जिसमें नॉन-फाइनल स्टेट एक्सिस्टेंसिअल और यूनिवर्सल स्टेट में डिवाइड होती हैं। यह अंततः अपने वर्तमान कॉन्फ़िगरेशन से एक्सेप्टिंग कर रहा है यदि: यह एक्सिस्टेंसिअल स्टेट में है और कुछ अंततः स्वीकार्य कॉन्फ़िगरेशन में परिवर्तित हो सकता है; या, यह यूनिवर्सल स्टेट में है और प्रत्येक संक्रमण अंततः कुछ स्वीकार्य विन्यास में होता है; या, यह एक्सेप्टिंग स्टेट में है।[3]

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

यदि हम एक्सिस्टेंसिअल और यूनिवर्सल स्टेट के मध्य अधिकतम k-1 स्वैप की आवश्यकता को ओमिट कर देते हैं, जिससे कि हमें केवल यह आवश्यक हो कि हमारी अल्टरनेटिंग ट्यूरिंग मशीन पॉलीनोमिअल टाइम में चले, तो हमारे पास क्लास 'एपी' की परिभाषा है, जो 'पीस्पेस' के समान है।[5]

पॉलीनोमिअल हायरार्की में क्लासेस के मध्य संबंध

पॉलीनोमिअल टाइम हायरार्की के एक्विवैलेन्ट कम्यूटेटिव डायग्राम। एरो इन्क्लुज़न को दर्शाते हैं।

पॉलीनोमिअल हायरार्की में सभी क्लासेस का मिलन कम्प्लेक्सिटी क्लास PH है।

परिभाषाएँ संबंधों का सिग्नल देती हैं:

अर्थमेटिक और एनालिटिक हायरार्की के विपरीत, जिनके इन्क्लूज़न को उचित माना जाता है, यह ओपन प्रश्न है कि क्या इनमें से कोई भी इन्क्लूज़न उचित है, चूँकि यह व्यापक रूप से माना जाता है कि वे सभी हैं। यदि कोई , या यदि कोई है, तब हायरार्की सभी के लिए लेवल k: तक आवश्यक हो जाता है , है।[6] विशेष रूप से, हमारे पास अनसाल्व्ड प्रॉब्लम से जुड़े निम्नलिखित इम्प्लिकेशन्स हैं:

  • P = NP यदि और केवल P = PH है।[7]
  • यदि NP = co-NP तो NP = PH है। (co-NP है)

वह स्टेट जिसमें NP = PH को PH के दूसरे लेवल तक कोलैप्स भी कहा जाता है। स्टेट P = NP, PH से P के कोलैप्स से युग्मित होता है।

Unsolved problem in computer science:

(more unsolved problems in computer science)

प्रथम लेवल तक कोलैप्स का प्रश्न सामान्यतः अधिक कठिन माना जाता है। अधिकांश शोधकर्ता दूसरे लेवल तक भी कोलैप्स में विश्वास नहीं करते हैं।

अन्य क्लासेस से संबंध

See also: पीएच (समष्टिता) अन्य वर्गों से संबंध
Unsolved problem in computer science:

(more unsolved problems in computer science)
P, NP, co-NP, BPP, P/poly, PH, और पीएसपीएसीई सहित कम्प्लेक्सिटी क्लासेस का हैस आरेख है।

पॉलीनोमिअल हायरार्की एक्सपोनेंशियल हायरार्की और अर्थमेटिक हायरार्की का एनालॉग (अधिक लोअर कम्प्लेक्सिटी पर) है।

यह ज्ञात है कि PH पीस्पेस के अंदर कॉन्टेंड है, किन्तु यह ज्ञात नहीं है कि दोनों क्लास समान हैं या नहीं हैं। इस प्रॉब्लम का उपयोगी सुधार यह है कि PH = पीस्पेस यदि और केवल परिमित संरचनाओं पर दूसरे क्रम के लॉजिक कोट्रान्सिटीव क्लोज़र ऑपरेटर के अतिरिक्त कोई शक्ति नहीं मिलती है।

यदि पॉलीनोमिअल हायरार्की में कोई कम्पलीट प्रॉब्लम है, तो इसमें केवल लिमिटेड रूप से कई भिन्न-भिन्न लेवल हैं। चूंकि पीएसपीएसीई-कम्पलीट प्रॉब्लम्स हैं, हम जानते हैं कि यदि पीएसपीएसीई = PH, तो पॉलीनोमिअल हायरार्की अवश्य होना चाहिए, क्योंकि पीएसपीएसीई-कम्पलीट प्रॉब्लम होगी -कुछ k के लिए कम्पलीट प्रॉब्लम है।[8]

पॉलीनोमिअल हायरार्की में प्रत्येक क्लास में सम्मिलित हैं -कम्पलीट प्रॉब्लम्स (पॉलीनोमिअल-टाइम अनेक-रिडक्शन के अंतर्गत कम्पलीट प्रॉब्लम्स) हैं। इसके अतिरिक्त, पॉलीनोमिअल हायरार्की में प्रत्येक क्लास के अंतर्गत विवृत -कटौती है: जिसका अर्थ है कि हायरार्की में क्लास C और लैंग्वेज के लिए, यदि , तब होता है। ये दोनों तथ्य मिलकर यह दर्शाते हैं कि यदि के लिए कम्पलीट प्रॉब्लम , तब , और है। उदाहरण के लिए, है। दूसरे शब्दों में, यदि किसी लैंग्वेज को C में किसी ओरेकल के आधार पर परिभाषित किया जाता है, तो हम मान सकते हैं कि इसे C के लिए कम्पलीट प्रॉब्लम के आधार पर परिभाषित किया जाता है। इसलिए कम्पलीट प्रॉब्लम्स उस क्लास के रिप्रेजेन्टेटिव के रूप में वर्क करती हैं जिसके लिए वे कम्पलीट हैं।

सिप्सर-लॉटमैन प्रमेय में कहा गया है कि क्लास बीपीपी पॉलीनोमिअल हायरार्की के दूसरे लेवल में कॉन्टेंड है।

कन्नन के प्रमेय में कहा गया है कि किसी भी k के लिए, SIZE(nk) में सम्मिलित नहीं है।

टोडा के प्रमेय में कहा गया है कि पॉलीनोमिअल हायरार्की P#P में कॉन्टेंड है।

प्रॉब्लम्स

  • An example of a natural problem in is circuit minimization: given a number k and a circuit A computing a Boolean function f, determine if there is a circuit with at most k gates that computes the same function f. Let C be the set of all boolean circuits. The language

    is decidable in polynomial time. The language

    is the circuit minimization language. because L is decidable in polynomial time and because, given , if and only if there exists a circuit B such that for all inputs x, .
  • A complete problem for is satisfiability for quantified Boolean formulas with k – 1 alternations of quantifiers (abbreviated QBFk or QSATk). This is the version of the boolean satisfiability problem for . In this problem, we are given a Boolean formula f with variables partitioned into k sets X1, ..., Xk. We have to determine if it is true that
    That is, is there an assignment of values to variables in X1 such that, for all assignments of values in X2, there exists an assignment of values to variables in X3, ... f is true? The variant above is complete for . The variant in which the first quantifier is "for all", the second is "exists", etc., is complete for . Each language is a subset of the problem obtained by removing the restriction of k – 1 alternations, the PSPACE-complete problem TQBF.
  • A Garey/Johnson-style list of problems known to be complete for the second and higher levels of the polynomial hierarchy can be found in this Compendium.

यह भी देखें

संदर्भ

सामान्य सन्दर्भ

  1. Arora, Sanjeev; Barak, Boaz (2009). जटिलता सिद्धांत: एक आधुनिक दृष्टिकोण. Cambridge University Press. ISBN 978-0-521-42426-4. खंड 1.4, "स्ट्रिंग्स के रूप में मशीनें और सार्वभौमिक ट्यूरिंग मशीन" और 1.7, "प्रमेय का प्रमाण 1.9"
  2. अल्बर्ट आर. मेयर|ए. आर. मेयर और लैरी स्टॉकमेयर|एल. जे. स्टॉकमेयर. क्लास के साथ नियमित अभिव्यक्तियों के लिए समतुल्यता प्रॉब्लम के लिए घातांकीय स्थान की आवश्यकता होती है। स्विचिंग और ऑटोमेटा थ्योरी पर 13वीं आईईईई संगोष्ठी की कार्यवाही में, पृष्ठ 125-129, 1972। वह पेपर जिसने पॉलीनोमिअल हायरार्की का परिचय दिया।
  3. लैरी स्टॉकमेयर|एल. जे. स्टॉकमेयर. :doi:10.1016/0304-3975(76)90061-X|पॉलीनोमिअल-टाइम हायरार्की। सैद्धांतिक कंप्यूटर विज्ञान, खंड 3, पृष्ठ 1-22, 1976।
  4. क्रिस्टोस पापादिमित्रीउ|सी. पापादिमित्रीउ. अभिकलनात्मक कम्प्लेक्सिटी। एडिसन-वेस्ले, 1994। अध्याय 17. पॉलीनोमिअल हायरार्की, पीपी. 409-438।
  5. Michael R. Garey and David S. Johnson (1979). कंप्यूटर और इंट्रेक्टेबिलिटी: एनपी-पूर्णता के सिद्धांत के लिए एक गाइड. W.H. Freeman. ISBN 0-7167-1045-5. धारा 7.2: पॉलीनोमिअल हायरार्की, पृष्ठ 161-167।

उद्धरण

  1. ↑ Arora and Barak, 2009, pp.97
  2. ↑ Completeness in the Polynomial-Time Hierarchy A Compendium, M. Schaefer, C. Umans
  3. ↑ Arora and Barak, pp.99–100
  4. ↑ Arora and Barak, pp.100
  5. ↑ Arora and Barak, pp.100
  6. ↑ Arora and Barak, 2009, Theorem 5.4
  7. ↑ Hemaspaandra, Lane (2018). "17.5 Complexity classes". In Rosen, Kenneth H. (ed.). असतत और संयुक्त गणित की पुस्तिका. Discrete Mathematics and Its Applications (2nd ed.). CRC Press. pp. 1308–1314. ISBN 9781351644051.
  8. ↑ Arora and Barak, 2009, Claim 5.5
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=बहुपद_पदानुक्रम&oldid=281346’