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

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

मात्राबद्ध बूलियन सूत्र परिभाषा

बहुपद पदानुक्रम की अस्तित्वगत/सार्वभौमिक परिभाषा के लिए, आइए 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}}$, जहां एल^cL का पूरक है।

होने देना 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\}$.

वर्ग एनपी (जटिलता) और सह-एनपी को इस प्रकार परिभाषित किया जा सकता है ${\mathsf {NP}}=\exists ^{\mathsf {P}}{\mathsf {P}}$, और ${\mathsf {coNP}}=\forall ^{\mathsf {P}}{\mathsf {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}}$.

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

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

एक वैकल्पिक ट्यूरिंग मशीन एक गैर-नियतात्मक ट्यूरिंग मशीन है जिसमें गैर-अंतिम अवस्थाएँ अस्तित्वगत और सार्वभौमिक अवस्थाओं में विभाजित होती हैं। यह अंततः अपने वर्तमान कॉन्फ़िगरेशन से स्वीकार कर रहा है यदि: यह एक अस्तित्वगत स्थिति में है और कुछ अंततः स्वीकार्य कॉन्फ़िगरेशन में परिवर्तित हो सकता है; या, यह एक सार्वभौमिक स्थिति में है और प्रत्येक संक्रमण अंततः कुछ स्वीकार्य विन्यास में होता है; या, यह स्वीकार्य स्थिति में है। हम परिभाषित करते हैं $\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}}$. विशेष रूप से, हमारे पास अनसुलझी समस्याओं से जुड़े निम्नलिखित निहितार्थ हैं:

• पी बनाम एनपी समस्या|पी = एनपी यदि और केवल यदि पी = पीएच।
• यदि एनपी = सह-एनपी तो एनपी = पीएच। (सह-एनपी है $\Pi _{1}^{\mathsf {P}}$.)

वह मामला जिसमें एनपी = पीएच को पीएच के दूसरे स्तर तक पतन भी कहा जाता है। मामला P = NP, PH से P के पतन से मेल खाता है।

Unsolved problem in computer science:

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

(more unsolved problems in computer science)

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

अन्य वर्गों से संबंध

See also: PH (complexity) § Relationship to other classes

Unsolved problem in computer science:

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

(more unsolved problems in computer science)

पी (जटिलता), एनपी (जटिलता), सह-एनपी, बीपीपी (जटिलता), पी/पॉली, पीएच (जटिलता), और पीएसपीएसीई सहित जटिलता वर्गों का हैस आरेख

बहुपद पदानुक्रम घातीय पदानुक्रम और अंकगणितीय पदानुक्रम का एक एनालॉग (बहुत कम जटिलता पर) है।

यह ज्ञात है कि PH PSPACE के भीतर समाहित है, लेकिन यह ज्ञात नहीं है कि दोनों वर्ग समान हैं या नहीं। इस समस्या का एक उपयोगी सुधार यह है कि PH = PSPACE यदि और केवल यदि SO (जटिलता) | परिमित संरचनाओं पर दूसरे क्रम के तर्क को सकर्मक समापन ऑपरेटर के अतिरिक्त कोई अतिरिक्त शक्ति नहीं मिलती है।

यदि बहुपद पदानुक्रम में कोई पूर्ण समस्या है, तो इसमें केवल सीमित रूप से कई अलग-अलग स्तर हैं। चूंकि पीएसपीएसीई-पूर्ण समस्याएं हैं, हम जानते हैं कि यदि पीएसपीएसीई = पीएच, तो बहुपद पदानुक्रम ढह जाना चाहिए, क्योंकि पीएसपीएसीई-पूर्ण समस्या एक होगी $\Sigma _{k}^{\mathsf {P}}$-कुछ के लिए पूरी समस्या। बहुपद पदानुक्रम में प्रत्येक वर्ग में शामिल हैं $\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) में शामिल नहीं है^क).

टोडा के प्रमेय में कहा गया है कि बहुपद पदानुक्रम पी में निहित है^#पी.

समस्याएँ

• 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।