पी-पूर्ण

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

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

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

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

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

प्रेरणा

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

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

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

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

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

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

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

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

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

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

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

समस्याएँ पी-पूर्ण होने के लिए ज्ञात नहीं हैं

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

संदर्भ

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