पी-पूर्ण

संगणनात्मक जटिलता सिद्धांत में, एक निर्णय समस्या पी-पूर्ण है (जटिलता वर्ग पी के लिए (पूर्ण (जटिलता)) है यदि यह पी में है और पी में हर समस्या उचित अभाव से अभाव (जटिलता) हो सकती है।

पी-पूर्ण निर्णय समस्याओं की धारणा विश्लेषण में उपयोगी है:

• किन समस्याओं को प्रभावी ढंग से समानांतर करना जटिल है,
• सीमित स्थान में किन समस्याओं को समाधित करना जटिल है।

विशेष रूप से जब बहुअवधि- समानेयता की अनुपात में समानेयता की प्रबल धारणा पर विचार किया जाता है।

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

प्रेरणा

श्रेणी पी, सामान्यतः अनुक्रमिक संगणक के लिए सभी सरल समस्याओं को सम्मिलित करने के लिए लिया जाता है, जिसमें श्रेणी एनसी सम्मिलित होती है, जिसमें उन समस्याओं का समावेश होता है जिन्हें समांतर संगणक पर कुशलतापूर्वक समाधित किया जा सकता है। ऐसा इसलिए है क्योंकि समानांतर संगणकों को अनुक्रमिक यंत्र पर अनुकरण किया जा सकता है।यह ज्ञात नहीं है कि एनसी = पी। दूसरे शब्दों में, यह ज्ञात नहीं है कि क्या कोई सरल समस्याएं हैं जो स्वाभाविक रूप से अनुक्रमिक हैं। जिस तरह यह व्यापक रूप से संदेह है कि P, NP के बराबर नहीं है, उसी तरह व्यापक रूप से यह संदेह है कि NC, P के बराबर नहीं है।

इसी तरह, श्रेणी एल (जटिलता) में वे सभी समस्याएं सम्मिलित हैं जिन्हें लघुगणक अंतराल में अनुक्रमिक संगणक द्वारा समाधित किया जा सकता है। ऐसी यंत्रों बहुपद अवधि में चलती हैं क्योंकि उनके पास विन्यासों की बहुपद संख्या हो सकती है। ऐसा संदेह है कि L ≠ P; अर्थात्, कुछ समस्याएँ जिन्हें बहुपद अवधि में समाधित किया जा सकता है, उन्हें भी लघुगणक स्थान से अधिक की आवश्यकता होती है।

इसी तरह पी = एनपी संदेह का विश्लेषण करने के लिए एनपी-पूर्ण समस्याओं के उपयोग के लिए, पी-पूर्ण समस्याओं को संभवतः समानांतर नहीं या संभवतः अंतर्निहित अनुक्रमिक समस्याओं के रूप में देखा जाता है, इसी तरह से एनसी = पी संदेह का अध्ययन करने के लिए कार्य करता है। कुछ पी-पूर्ण समस्या के समाधान को समानांतर करने का एक कुशल विधि खोजने से पता चलेगा कि एनसी = पी। इसे उत्तम लघुगणक अंतराल की आवश्यकता वाली समस्याओं के रूप में भी सोचा जा सकता है; पी-पूर्ण समस्या के लिए एक अभिलेख -अंतराल समाधान (अभिलेख -अंतराल पुनःस्थापन के आधार पर परिभाषा का उपयोग करके) एल = पी का अर्थ होगा।

इसके पीछे तर्क तर्क के समान है कि एक एनपी-पूर्ण समस्या का बहुपद-अवधि समाधान पी = एनपी सिद्ध होगा: यदि हमारे पास पी में किसी भी समस्या से एक समस्या ए में एनसी अभाव है, और ए के लिए एक एनसी समाधान है, तो एनसी = पी। इसी प्रकार, यदि हमारे पास पी में किसी समस्या से समस्या ए में अभिलेख -अंतराल अभाव है, और ए के लिए अभिलेख -अंतराल समाधान है, तो एल = पी।

पी-पूर्ण समस्याएं

अभिलेख अंतराल के अंतर्गत सबसे मूलभूत पी-पूर्ण समस्या अनेक-एक पुनःस्थापन निम्न है: एक परिगणन यंत्र दी गई है $M$, उस यंत्र x के लिए एक सहयोग, और एक नंबर T (एकल अंक प्रणाली में लिखा गया), $\langle M,x,T\rangle$ क्या वह यंत्र पहले टी चरणों में उस सहयोग पर संवृत है? किसी भी एक्स के लिए $L$ पी में, परिगणन यंत्र के संकेतीकरण को उत्पादन करें जो इसे बहुपद-अवधि में स्वीकार करता है, एक्स का संकेतीकरण और अनेक चरण $T=p(|x|)$ पी के अनुरूप जो परिगणन यंत्र के संचालन पर बहुपद-समयबद्ध है $M_{L}$ निर्णय लेने से $L$, $\langle M,x,p(|x|)\rangle$. यंत्र M अंदर x पर संवृत है $p(|x|)$ चरण यद्यपि और केवल यद्यपि एक्स एल में है। स्पष्ट रूप से, यद्यपि हम अनुक्रमिक संगणक के सामान्य अनुकरण (अर्थात परिगणन यंत्र के परिगणन यंत्र अनुकरण ) को समानांतर कर सकते हैं, तो हम उस संगणक पर चलने वाले किसी भी सभा को समानांतर करने में सक्षम होंगे . यदि यह समस्या एनसी में है, तो पी में हर दूसरी समस्या भी है। यदि द्विचर में चरणों की संख्या लिखी जाती है, तो समस्या अपेक्षा अवधि-पूर्ण होती है।यह समस्या पी-पूर्णता के सिद्धांत में एक सामान्य गति को दर्शाती है। हम वास्तव में इस बात में दिलचस्पी नहीं रखते हैं कि समानांतर यंत्र पर समस्या को शीघ्र से समाधित किया जा सकता है या नहीं। हम सिर्फ इस बात में रुचि रखते हैं कि क्या एक समानांतर यंत्र एक अनुक्रमिक यंत्र की अनुपात में इसे 'बहुत अधिक' शीघ्र से समाधित करती है। इसलिए, हमें समस्या को फिर से लिखना होगा कि अनुक्रमिक संस्करण पी में हो। यही कारण है कि इस समस्या को 'टी' को एकल में लिखा जाना आवश्यक है। यदि एक संख्या T को एक द्विआधारी अंक प्रणाली संख्या ("n वाले और शून्य की एक कङी, जहां n= log T) के रूप में लिखा जाता है, तो स्पष्ट अनुक्रमिक कलन विधि कर सकते हैं अवधि लेना 2ⁿ. दूसरी ओर, यदि T को एक एकल संख्या (n वाले की एक कङी, जहाँ n = T) के रूप में लिखा जाता है, तो इसमें केवल अवधि n लगता है। द्विचर के अतिरिक्त एकल में T लिखकर, हमने स्पष्ट अनुक्रमिक कलन विधि को घातीय अवधि से रैखिक अवधि तक कम कर दिया है। यह अनुक्रमिक समस्या को 'P' में रखता है। फिर, यह 'एनसी' में होगा यद्यपि और केवल यद्यपि यह समांतर है।

अनेक अन्य समस्याएं 'पी'-पूर्ण सिद्ध हुई हैं, और इसलिए व्यापक रूप से स्वाभाविक अनुक्रमिक मानी जाती हैं। इनमें सम्मिलित हैं निम्नलिखित समस्याएँ जो कम से कम अभिलेख अंतराल पुनःस्थापन के अंतर्गत 'पी'-पूर्ण हैं, जैसा कि दिया गया है, या निर्णय-समस्या के रूप में:

• परिपथ महत्व समस्या (सीवीपी) - एक परिपथ दिया गया है, परिपथ में सहयोग और परिपथ में एक मार्ग, उस मार्ग के उत्पादन की गणना करें।
• सीवीपी का प्रतिबंधित मामला - सीवीपी की तरह, प्रत्येक मार्ग को छोड़कर दो सहयोग और दो उत्पादन (एफ और रहित एफ) हैं, हर दूसरी परत सिर्फ और मार्ग है, स्थिरता या मार्ग हैं (या, समकक्ष, सभी मार्ग तथा पूरक मार्ग हैं, या सभी द्वार एनओआर द्वार हैं), एक द्वार के सहयोग तत्काल पूर्ववर्ती परत से आते हैं
• रैखिक कार्यरचना - रैखिक असमानता बाधाओं के अधीन एक रैखिक कार्य को अधिकतम करें
• कोशक्रमानुसार प्रथम मध्यमार्ग पहले खोज आदेश - निश्चित आदेशित आसन्न सूचियों और बिंदु यू और वी के साथ एक लेखाचित्र सिद्धांत को देखते हुए, क्या शीर्ष यू ने मध्यमार्ग-प्रथम खोज में शीर्ष वी से पहले उपस्थिति किया है, जो आसन्न सूचियों के क्रम से प्रेरित है?
• संदर्भ मुक्त व्याकरण सदस्यता - एक संदर्भ मुक्त व्याकरण और एक कङी को देखते हुए, क्या वह कङी उस व्याकरण द्वारा उत्पन्न की जा सकती है?
• हॉर्न-संतुष्टि - हॉर्न क्लॉज का एक समूह दिया गया है, क्या कोई परिवर्तनीय कार्य है जो उन्हें संतुष्ट करता है? यह बूलियन संतुष्टि समस्या का Ps संस्करण है।
• चाल का जीवनकाल - कॉनवे के चाल का जीवनकाल के प्रारंभिक विन्यास को देखते हुए, एक विशेष कक्ष, और एक अवधि टी (एकल में), क्या वह कक्ष टी चरणों के बाद सचेत है?
• एलजेडडब्लू (कलन विधि) (1978 प्रतिमान) आंकड़े संपीड़न - दिए गए कङी s और t, एलजेड78 विधि के साथ s को संपीड़ित करने से शब्दकोश में t जुड़ जाएगा? (ध्यान दें कि एलजेड77 संपीड़न जैसे कि जी ज़िप के लिए, यह बहुत आसान है, क्योंकि समस्या एस में टी है? तक कम हो जाती है।)
• आंशिक प्रकार के लिए प्रकार का अनुमान - लैम्ब्डा गणना से एक प्रकार सिद्धांत शब्द दिया गया है, यह निर्धारित करें कि इस शब्द का आंशिक प्रकार है या नहीं।ं

ऊपर दी गई अधिकांश शैलियाँ 'पी' हैं - अभाव की और भी प्रबल धारणाओं के अंतर्गत, जैसे कि समरूप $AC^{0}$ अनेक-एक पुनःस्थापन, डलॉग अवधि पुनःस्थापन, या बहुलघुगणकीय प्रक्षेपण।

यह सिद्ध करने के लिए कि पी में दी गई समस्या पी-पूर्ण है, सामान्यतः एक ज्ञात पी-पूर्ण समस्या को कम करने की कोशिश की जाती है।

1999 में, जिन-यी कै और डी. शिवकुमार, ओगिहारा द्वारा कार्य पर निर्माण कर रहे थे, ने दिखाया कि यद्यपि कोई विरल भाषा उपस्थितहै जो पी-पूर्ण है, तो एल = पी। पी-पूर्ण समस्याएं अलग-अलग अवधि जटिलता के साथ समाधित करने योग्य हो सकती हैं। उदाहरण के लिए, परिपथ महत्व समस्या को संस्थानिक प्रकार द्वारा रैखिक अवधि में समाधित किया जा सकता है। निस्संदेह, क्योंकि पी-पूर्ण समस्या में पुनःस्थापन में अलग-अलग अवधि की जटिलताएं हो सकती हैं, इस तथ्य का अर्थ यह नहीं है कि पी में सभी समस्याओं को रैखिक अवधि में भी समाधित किया जा सकता है।

== पी-पूर्ण == के रूप में ज्ञात समस्याएं नहीं

कुछ एनपी-समस्याओं को या तो एनपी-पूर्ण या पी में नहीं जाना जाता है। इन समस्याओं (जैसे पूर्णांक गुणनखंडन, लेखाचित्र समरूपता, समता खेल) के कठिन होने का संदेह है. इसी तरह पी में ऐसी समस्याएं हैं जो या तो पी-पूर्ण या एनसी के रूप में नहीं जानी जाती हैं, किन्तुउन्हें समानांतर करना जटिल माना जाता है। उदाहरणों में दो संख्याओं का सबसे बड़ा सामान्य विभाजक खोजने के निर्णय समस्या रूप सम्मिलित हैं, यह निर्धारित करना कि विस्तारित यूक्लिडियन कलन विधि दो संख्याओं के दिए जाने पर क्या उत्तर देगा, और बड़े पूर्णांक भार वाले लेखाचित्र के अधिकतम भार मिलान की गणना करेगा।

संदर्भ

• Greenlaw, Raymond, James Hoover, and Walter Ruzzo. 1995. Limits To Parallel computation; P-Completeness Theory. ISBN 0-19-508591-4. — Develops the theory, then catalogs 96 P-Complete problems.
• Satoru Miyano, Shuji Shiraishi, and Takayoshi Shoudai. A List of P-Complete Problems. Kyushu University, RIFIS-TR-CS-17. December 1990.