पी-पूर्ण

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

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

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

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

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

प्रेरणा

कक्षा पी, आमतौर पर अनुक्रमिक कंप्यूटर के लिए सभी ट्रैक्टेबल समस्याओं को शामिल करने के लिए लिया जाता है, जिसमें कक्षा एनसी शामिल होती है, जिसमें उन समस्याओं का समावेश होता है जिन्हें समांतर कंप्यूटर पर कुशलतापूर्वक हल किया जा सकता है। ऐसा इसलिए है क्योंकि समानांतर कंप्यूटरों को अनुक्रमिक मशीन पर अनुकरण किया जा सकता है। यह ज्ञात नहीं है कि एनसी = पी। दूसरे शब्दों में, यह ज्ञात नहीं है कि क्या कोई ट्रैक्टेबल समस्याएं हैं जो स्वाभाविक रूप से अनुक्रमिक हैं। जिस तरह यह व्यापक रूप से संदेह है कि 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|)$ कदम अगर और केवल अगर एक्स एल में है। स्पष्ट रूप से, अगर हम अनुक्रमिक कंप्यूटर के सामान्य सिमुलेशन (यानी ट्यूरिंग मशीन के ट्यूरिंग मशीन सिमुलेशन) को समानांतर कर सकते हैं, तो हम उस कंप्यूटर पर चलने वाले किसी भी प्रोग्राम को समानांतर करने में सक्षम होंगे . यदि यह समस्या एनसी में है, तो पी में हर दूसरी समस्या भी है। यदि बाइनरी में चरणों की संख्या लिखी जाती है, तो समस्या EXPTIME-पूर्ण होती है। यह समस्या पी-पूर्णता के सिद्धांत में एक सामान्य चाल को दर्शाती है। हम वास्तव में इस बात में दिलचस्पी नहीं रखते हैं कि समानांतर मशीन पर समस्या को जल्दी से हल किया जा सकता है या नहीं। हम सिर्फ इस बात में रुचि रखते हैं कि क्या एक समानांतर मशीन एक अनुक्रमिक मशीन की तुलना में इसे 'बहुत अधिक' तेजी से हल करती है। इसलिए, हमें समस्या को फिर से लिखना होगा ताकि अनुक्रमिक संस्करण पी में हो। यही कारण है कि इस समस्या को 'टी' को यूनरी में लिखा जाना आवश्यक है। यदि एक संख्या T को एक द्विआधारी अंक प्रणाली संख्या ("n वाले और शून्य की एक स्ट्रिंग, जहां n= log T) के रूप में लिखा जाता है, तो स्पष्ट अनुक्रमिक एल्गोरिदम कर सकते हैं समय लेना 2^एन. दूसरी ओर, यदि T को एक एकल संख्या (n वाले की एक स्ट्रिंग, जहाँ n = T) के रूप में लिखा जाता है, तो इसमें केवल समय n लगता है। बाइनरी के बजाय यूनरी में टी लिखकर, हमने स्पष्ट अनुक्रमिक एल्गोरिदम को घातीय समय से रैखिक समय तक कम कर दिया है। यह अनुक्रमिक समस्या को 'पी' में रखता है। फिर, यह 'एनसी' में होगा अगर और केवल अगर यह समांतर है।

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

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

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

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

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.