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

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