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

From Vigyanwiki
No edit summary
 
(4 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''' डिनोट किया गया है।


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


==परिभाषाएँ==
==परिभाषाएँ==
Line 16: Line 16:
:<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>सेट 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>
जहां <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> है, जहां L<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> है।


'''NP''' और  '''co-NP''' को इस प्रकार <math> \mathsf{NP} = \exists^\mathsf{P} \mathsf{P} </math>, और <math> \mathsf{coNP} = \forall^\mathsf{P} \mathsf{P} </math> परिभाषित किया जा सकता है, जहां '''P''' सभी संभावित (पॉलीनोमिअल-टाइम) डिसिशन योग्य लैंग्वेज का क्लास है। पॉलीनोमिअल हायरार्की को पुनरावर्ती रूप से परिभाषित किया जा सकता है:
'''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>
Line 41: Line 41:
ध्यान दें कि <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 के अनुरूप भूमिका निभाते है। [[बेयर स्पेस (सेट सिद्धांत)|वास्तविक संख्याओं]] के सबसेट का हायरार्की देने के लिए [[विश्लेषणात्मक पदानुक्रम|विश्लेषणात्मक हायरार्की]] को भी इसी प्रकार से परिभाषित किया गया है।
यह परिभाषा पॉलीनोमिअल हायरार्की और अर्थमेटिक हायरार्की के मध्य घनिष्ठ संबंध को दर्शाती है, जहां निर्णायक लैंग्वेज और रेकर्सिवली कैलक्यूलेशन योग्य लैंग्वेज क्रमशः 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>
हम <math>\Sigma_k^\mathsf{P}</math> परिभाषित करते हैं पॉलीनोमिअल टाइम में अल्टरनेटिंग ट्यूरिंग मशीन द्वारा एक्सेप्टिंग लैंग्वेज का क्लास होने के लिए जैसे कि प्रारंभिक स्टेट एक्सिस्टेंसिअल स्टेट है और प्रत्येक एड्रेस मशीन एक्सिस्टेंसिअल और यूनिवर्सल स्टेट के मध्य अधिकतम k - 1 बार स्वैप ले सकती है। हम परिभाषित करते हैं <math>\Pi_k^\mathsf{P}</math> इसी प्रकार, अतिरिक्त इसके कि प्रारंभिक स्टेट यूनिवर्सल स्टेट है।<ref>Arora and Barak, pp.100</ref>


यदि हम अस्तित्वगत और सार्वभौमिक अवस्थाओं के मध्य अधिकतम k-1 स्वैप की आवश्यकता को त्याग देते हैं, जिससे कि हमें केवल यह आवश्यक हो कि हमारी वैकल्पिक ट्यूरिंग मशीन पॉलीनोमिअल टाइम में चले, तो हमारे पास क्लास '<nowiki/>'''एपी'''<nowiki/>' की परिभाषा है, जो ''''पीस्पेस'''<nowiki/>' के समान है।<ref>Arora and Barak, pp.100</ref>
यदि हम एक्सिस्टेंसिअल और यूनिवर्सल स्टेट के मध्य अधिकतम k-1 स्वैप की आवश्यकता को ओमिट कर देते हैं, जिससे कि हमें केवल यह आवश्यक हो कि हमारी अल्टरनेटिंग ट्यूरिंग मशीन पॉलीनोमिअल टाइम में चले, तो हमारे पास क्लास '<nowiki/>'''एपी'''<nowiki/>' की परिभाषा है, जो ''''पीस्पेस'''<nowiki/>' के समान है।<ref>Arora and Barak, pp.100</ref>


== पॉलीनोमिअल हायरार्की में क्लासेस के मध्य संबंध ==
== पॉलीनोमिअल हायरार्की में क्लासेस के मध्य संबंध ==
[[Image:Polynomial time hierarchy.svg|250px|thumb|right|पॉलीनोमिअल टाइम हायरार्की के समतुल्य क्रमविनिमेय आरेख। तीर समावेशन को दर्शाते हैं।]]पॉलीनोमिअल हायरार्की में सभी क्लासेस का मिलन कम्प्लेक्सिटी क्लास '''PH''' है।
[[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> विशेष रूप से, हमारे पास अनसाल्व्ड प्रॉब्लम से जुड़े निम्नलिखित इम्प्लिकेशन्स हैं:


* '''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>
* '''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>
* यदि '''NP''' =  '''co-NP''' तो '''NP''' = '''PH''' है। ('''co-NP''' <math>\Pi_1^\mathsf{P}</math>है)
* यदि '''NP''' =  '''co-NP''' तो '''NP''' = '''PH''' है। ('''co-NP''' <math>\Pi_1^\mathsf{P}</math>है)
वह स्थिति जिसमें '''NP''' = '''PH''' को '''PH''' के दूसरे स्तर तक कोलैप्स भी कहा जाता है। स्थिति 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} }}}}


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


== अन्य क्लासेस से संबंध ==
== अन्य क्लासेस से संबंध ==
Line 72: Line 72:
{{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|P, NP,  co-NP, [[बीपीपी (जटिलता)|BPP]], P/poly, PH, और पीएसपीएसीई सहित कम्प्लेक्सिटी क्लासेस का हैस आरेख है।]]पॉलीनोमिअल हायरार्की [[घातीय पदानुक्रम|घातीय हायरार्की]] और अंकगणितीय हायरार्की का एनालॉग (अधिक अल्प कम्प्लेक्सिटी पर) है।
[[File:Complexity-classes-polynomial.svg|thumb|P, NP,  co-NP, [[बीपीपी (जटिलता)|BPP]], P/poly, PH, और पीएसपीएसीई सहित कम्प्लेक्सिटी क्लासेस का हैस आरेख है।]]पॉलीनोमिअल हायरार्की [[घातीय पदानुक्रम|एक्सपोनेंशियल हायरार्की]] और अर्थमेटिक हायरार्की का एनालॉग (अधिक लोअर कम्प्लेक्सिटी पर) है।


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


यदि पॉलीनोमिअल हायरार्की में कोई कम्पलीट प्रॉब्लम है, तो इसमें केवल सीमित रूप से कई भिन्न-भिन्न स्तर हैं। चूंकि पीएसपीएसीई-कम्पलीट प्रॉब्लम्स हैं, हम जानते हैं कि यदि पीएसपीएसीई = PH, तो पॉलीनोमिअल हायरार्की अवश्य होना चाहिए, क्योंकि पीएसपीएसीई-कम्पलीट प्रॉब्लम होगी <math>\Sigma_{k}^\mathsf{P}</math>-कुछ k के लिए कम्पलीट प्रॉब्लम है।<ref>Arora and Barak, 2009, Claim 5.5</ref>
यदि पॉलीनोमिअल हायरार्की में कोई कम्पलीट प्रॉब्लम है, तो इसमें केवल लिमिटेड रूप से कई भिन्न-भिन्न लेवल हैं। चूंकि पीएसपीएसीई-कम्पलीट प्रॉब्लम्स हैं, हम जानते हैं कि यदि पीएसपीएसीई = PH, तो पॉलीनोमिअल हायरार्की अवश्य होना चाहिए, क्योंकि पीएसपीएसीई-कम्पलीट प्रॉब्लम होगी <math>\Sigma_{k}^\mathsf{P}</math>-कुछ k के लिए कम्पलीट प्रॉब्लम है।<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>k</sup>) में सम्मिलित नहीं है।
कन्नन के प्रमेय में कहा गया है कि किसी भी k के लिए, <math>\Sigma_2</math> SIZE(n<sup>k</sup>) में सम्मिलित नहीं है।


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


==प्रॉब्लम्स==
==प्रॉब्लम्स==
Line 126: Line 126:
*[[एक्सटाइम]]
*[[एक्सटाइम]]
*घातांकीय हायरार्की
*घातांकीय हायरार्की
* [[अंकगणितीय पदानुक्रम|अंकगणितीय हायरार्की]]
* [[अंकगणितीय पदानुक्रम|अर्थमेटिक हायरार्की]]


==संदर्भ==
==संदर्भ==
Line 147: 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:

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

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

Unsolved problem 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