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

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