बहुपद पदानुक्रम

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

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

परिभाषाएँ

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

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

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

$\Delta _{0}^{\mathsf {P}}:=\Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}},$

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

$\Delta _{i+1}^{\mathsf {P}}:={\mathsf {P}}^{\Sigma _{i}^{\mathsf {P}}}$

$\Sigma _{i+1}^{\mathsf {P}}:={\mathsf {NP}}^{\Sigma _{i}^{\mathsf {P}}}$

$\Pi _{i+1}^{\mathsf {P}}:={\mathsf {coNP}}^{\Sigma _{i}^{\mathsf {P}}}$

जहां ${\mathsf {P}}^{\rm {A}}$ सेट A में किसी कम्पलीट प्रॉब्लम के लिए ओरेकल ऑगमेंटेड ट्यूरिंग मशीन द्वारा पॉलीनोमिअल टाइम में सॉल्व करने योग्य डिसिशन प्रॉब्लम का सेट है; क्लासेस ${\mathsf {NP}}^{\rm {A}}$ और ${\mathsf {coNP}}^{\rm {A}}$ को समान रूप से परिभाषित किया गया है। उदाहरण के लिए, $\Sigma _{1}^{\mathsf {P}}={\mathsf {NP}},\Pi _{1}^{\mathsf {P}}={\mathsf {coNP}}$, और $\Delta _{2}^{\mathsf {P}}={\mathsf {P^{NP}}}$ कुछ NP-कम्पलीट प्रॉब्लम के लिए ओरेकल के साथ डेटर्मीनिस्टिक ट्यूरिंग मशीन द्वारा पॉलीनोमिअल टाइम में सॉल्व की जाने वाली प्रॉब्लम का क्लास है।

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

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

$\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\},$

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

$\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\}$

ध्यान दें कि डी मॉर्गन का नियम मानता है: $\left(\exists ^{p}L\right)^{\rm {c}}=\forall ^{p}L^{\rm {c}}$ और $\left(\forall ^{p}L\right)^{\rm {c}}=\exists ^{p}L^{\rm {c}}$ है, जहां L^c L का कॉम्प्लीमेंट है।

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

$\exists ^{\mathsf {P}}{\mathcal {C}}:=\left\{\exists ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}$

$\forall ^{\mathsf {P}}{\mathcal {C}}:=\left\{\forall ^{p}L\ |\ p{\text{ is a polynomial and }}L\in {\mathcal {C}}\right\}$

पुनः, डी मॉर्गन का नियम कांस्टेंट हैं: ${\mathsf {co}}\exists ^{\mathsf {P}}{\mathcal {C}}=\forall ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}$ और ${\mathsf {co}}\forall ^{\mathsf {P}}{\mathcal {C}}=\exists ^{\mathsf {P}}{\mathsf {co}}{\mathcal {C}}$, जहां ${\mathsf {co}}{\mathcal {C}}=\left\{L^{c}|L\in {\mathcal {C}}\right\}$ है।

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

$\Sigma _{0}^{\mathsf {P}}:=\Pi _{0}^{\mathsf {P}}:={\mathsf {P}}$

$\Sigma _{k+1}^{\mathsf {P}}:=\exists ^{\mathsf {P}}\Pi _{k}^{\mathsf {P}}$

$\Pi _{k+1}^{\mathsf {P}}:=\forall ^{\mathsf {P}}\Sigma _{k}^{\mathsf {P}}$

ध्यान दें कि ${\mathsf {NP}}=\Sigma _{1}^{\mathsf {P}}$, और ${\mathsf {coNP}}=\Pi _{1}^{\mathsf {P}}$ है।

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

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

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

हम $\Sigma _{k}^{\mathsf {P}}$ परिभाषित करते हैं पॉलीनोमिअल टाइम में अल्टरनेटिंग ट्यूरिंग मशीन द्वारा एक्सेप्टिंग लैंग्वेज का क्लास होने के लिए जैसे कि प्रारंभिक स्टेट एक्सिस्टेंसिअल स्टेट है और प्रत्येक एड्रेस मशीन एक्सिस्टेंसिअल और यूनिवर्सल स्टेट के मध्य अधिकतम k - 1 बार स्वैप ले सकती है। हम परिभाषित करते हैं $\Pi _{k}^{\mathsf {P}}$ इसी प्रकार, अतिरिक्त इसके कि प्रारंभिक स्टेट यूनिवर्सल स्टेट है।

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

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

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

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

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

$\Sigma _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Sigma _{i+1}^{\mathsf {P}}$

$\Pi _{i}^{\mathsf {P}}\subseteq \Delta _{i+1}^{\mathsf {P}}\subseteq \Pi _{i+1}^{\mathsf {P}}$

$\Sigma _{i}^{\mathsf {P}}={\mathsf {co}}\Pi _{i}^{\mathsf {P}}$

अर्थमेटिक और एनालिटिक हायरार्की के विपरीत, जिनके इन्क्लूज़न को उचित माना जाता है, यह ओपन प्रश्न है कि क्या इनमें से कोई भी इन्क्लूज़न उचित है, चूँकि यह व्यापक रूप से माना जाता है कि वे सभी हैं। यदि कोई $\Sigma _{k}^{\mathsf {P}}=\Sigma _{k+1}^{\mathsf {P}}$, या यदि कोई $\Sigma _{k}^{\mathsf {P}}=\Pi _{k}^{\mathsf {P}}$ है, तब हायरार्की सभी के लिए लेवल k: तक आवश्यक हो जाता है $i>k$, $\Sigma _{i}^{\mathsf {P}}=\Sigma _{k}^{\mathsf {P}}$है। विशेष रूप से, हमारे पास अनसाल्व्ड प्रॉब्लम से जुड़े निम्नलिखित इम्प्लिकेशन्स हैं:

• P = NP यदि और केवल P = PH है।
• यदि NP = co-NP तो NP = PH है। (co-NP $\Pi _{1}^{\mathsf {P}}$है)

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

Unsolved problem in computer science:

${\mathsf {P}}{\overset {?}{=}}{\mathsf {NP}}$

(more unsolved problems in computer science)

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

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

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

Unsolved problem in computer science:

${\mathsf {PH}}{\overset {?}{=}}{\mathsf {PSPACE}}$

(more unsolved problems in computer science)

P, NP, co-NP, BPP, P/poly, PH, और पीएसपीएसीई सहित कम्प्लेक्सिटी क्लासेस का हैस आरेख है।

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

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

यदि पॉलीनोमिअल हायरार्की में कोई कम्पलीट प्रॉब्लम है, तो इसमें केवल लिमिटेड रूप से कई भिन्न-भिन्न लेवल हैं। चूंकि पीएसपीएसीई-कम्पलीट प्रॉब्लम्स हैं, हम जानते हैं कि यदि पीएसपीएसीई = PH, तो पॉलीनोमिअल हायरार्की अवश्य होना चाहिए, क्योंकि पीएसपीएसीई-कम्पलीट प्रॉब्लम होगी $\Sigma _{k}^{\mathsf {P}}$-कुछ k के लिए कम्पलीट प्रॉब्लम है।

पॉलीनोमिअल हायरार्की में प्रत्येक क्लास में सम्मिलित हैं $\leq _{\rm {m}}^{\mathsf {P}}$-कम्पलीट प्रॉब्लम्स (पॉलीनोमिअल-टाइम अनेक-रिडक्शन के अंतर्गत कम्पलीट प्रॉब्लम्स) हैं। इसके अतिरिक्त, पॉलीनोमिअल हायरार्की में प्रत्येक क्लास के अंतर्गत विवृत $\leq _{\rm {m}}^{\mathsf {P}}$-कटौती है: जिसका अर्थ है कि हायरार्की में क्लास C और लैंग्वेज $L\in {\mathcal {C}}$ के लिए, यदि $A\leq _{\rm {m}}^{\mathsf {P}}L$, तब $A\in {\mathcal {C}}$ होता है। ये दोनों तथ्य मिलकर यह दर्शाते हैं कि यदि $K_{i}$ के लिए कम्पलीट प्रॉब्लम $\Sigma _{i}^{\mathsf {P}}$, तब $\Sigma _{i+1}^{\mathsf {P}}={\mathsf {NP}}^{K_{i}}$, और $\Pi _{i+1}^{\mathsf {P}}={\mathsf {coNP}}^{K_{i}}$ है। उदाहरण के लिए, $\Sigma _{2}^{\mathsf {P}}={\mathsf {NP}}^{\mathsf {SAT}}$है। दूसरे शब्दों में, यदि किसी लैंग्वेज को C में किसी ओरेकल के आधार पर परिभाषित किया जाता है, तो हम मान सकते हैं कि इसे C के लिए कम्पलीट प्रॉब्लम के आधार पर परिभाषित किया जाता है। इसलिए कम्पलीट प्रॉब्लम्स उस क्लास के रिप्रेजेन्टेटिव के रूप में वर्क करती हैं जिसके लिए वे कम्पलीट हैं।

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

कन्नन के प्रमेय में कहा गया है कि किसी भी k के लिए, $\Sigma _{2}$ SIZE(n^k) में सम्मिलित नहीं है।

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

प्रॉब्लम्स

• An example of a natural problem in $\Sigma _{2}^{\mathsf {P}}$ 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

  $L=\left\{\langle A,k,B,x\rangle \in {\mathcal {C}}\times \mathbb {N} \times {\mathcal {C}}\times \{0,1\}^{*}\left|B{\text{ has at most }}k{\text{ gates, and }}A(x)=B(x)\right.\right\}$

  is decidable in polynomial time. The language

  ${\mathit {CM}}=\left\{\langle A,k\rangle \in {\mathcal {C}}\times \mathbb {N} \left|{\begin{matrix}{\text{there exists a circuit }}B{\text{ with at most }}k{\text{ gates }}\\{\text{ such that }}A{\text{ and }}B{\text{ compute the same function}}\end{matrix}}\right.\right\}$

  is the circuit minimization language. ${\mathit {CM}}\in \Sigma _{2}^{\mathsf {P}}(=\exists ^{\mathsf {P}}\forall ^{\mathsf {P}}{\mathsf {P}})$ because L is decidable in polynomial time and because, given $\langle A,k\rangle$, $\langle A,k\rangle \in {\mathit {CM}}$ if and only if there exists a circuit B such that for all inputs x, $\langle A,k,B,x\rangle \in L$.
• A complete problem for $\Sigma _{k}^{\mathsf {P}}$ is satisfiability for quantified Boolean formulas with k – 1 alternations of quantifiers (abbreviated QBF_k or QSAT_k). This is the version of the boolean satisfiability problem for $\Sigma _{k}^{\mathsf {P}}$. In this problem, we are given a Boolean formula f with variables partitioned into k sets X₁, ..., X_k. We have to determine if it is true that

  $\exists X_{1}\forall X_{2}\exists X_{3}\ldots f$

  That is, is there an assignment of values to variables in X₁ such that, for all assignments of values in X₂, there exists an assignment of values to variables in X₃, ... f is true? The variant above is complete for $\Sigma _{k}^{\mathsf {P}}$. The variant in which the first quantifier is "for all", the second is "exists", etc., is complete for $\Pi _{k}^{\mathsf {P}}$. 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।