पी-पूर्ण: Difference between revisions

From Vigyanwiki
 
No edit summary
 
(7 intermediate revisions by 3 users not shown)
Line 1: Line 1:
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक [[निर्णय समस्या]] जटिलता वर्ग पी (जटिलता) के लिए पी-पूर्ण ([[पूर्ण (जटिलता)]]) है यदि यह पी में है और पी में हर समस्या उचित कमी से [[कमी (जटिलता)]] हो सकती है।
[[कम्प्यूटेशनल जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]] में एक [[निर्णय समस्या|निर्णय निर्मेय]] पी-पूर्ण है (जटिलता वर्ग पी के लिए ([[पूर्ण (जटिलता)|पूर्ण जटिलता]]) है यदि यह पी में है तो पी में प्रत्येक निर्मेय उचित अभाव से [[कमी (जटिलता)|लघुकृत (जटिलता)]] करा जा सकता है।


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


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


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


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


== प्रेरणा ==
== प्रेरणा ==


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


इसी तरह, कक्षा एल (जटिलता) में वे सभी समस्याएं शामिल हैं जिन्हें लॉगरिदमिक स्पेस में अनुक्रमिक कंप्यूटर द्वारा हल किया जा सकता है। ऐसी मशीनें बहुपद समय में चलती हैं क्योंकि उनके पास विन्यासों की बहुपद संख्या हो सकती है। ऐसा संदेह है कि L ≠ 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 होगा।


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


लॉगस्पेस के तहत सबसे बुनियादी पी-पूर्ण समस्या कई-एक कटौती निम्न है: एक [[ट्यूरिंग मशीन]] दी गई है <math>M</math>, उस मशीन x के लिए एक इनपुट, और एक नंबर T ([[यूनरी अंक प्रणाली]] में लिखा गया), <math>\langle M,x,T \rangle</math> क्या वह मशीन पहले टी चरणों में उस इनपुट पर रुकती है? किसी भी एक्स के लिए <math>L</math> पी में, ट्यूरिंग मशीन के एन्कोडिंग को आउटपुट करें जो इसे बहुपद-समय में स्वीकार करता है, एक्स का एन्कोडिंग और कई चरण <math>T=p(|x|)</math> पी के अनुरूप जो ट्यूरिंग मशीन के संचालन पर बहुपद-समयबद्ध है <math>M_L</math> निर्णय लेने से <math>L</math>, <math>\langle M,x,p(|x|) \rangle</math>. मशीन M अंदर x पर रुकती है <math>p(|x|)</math> कदम अगर और केवल अगर एक्स एल में है। स्पष्ट रूप से, अगर हम अनुक्रमिक कंप्यूटर के सामान्य सिमुलेशन (यानी ट्यूरिंग मशीन के ट्यूरिंग मशीन सिमुलेशन) को समानांतर कर सकते हैं, तो हम उस कंप्यूटर पर चलने वाले किसी भी प्रोग्राम को समानांतर करने में सक्षम होंगे . यदि यह समस्या एनसी में है, तो पी में हर दूसरी समस्या भी है। यदि बाइनरी में चरणों की संख्या लिखी जाती है, तो समस्या EXPTIME-पूर्ण होती है।
अभिलेख अंतराल के अंतर्गत सबसे मूलभूत पी-पूर्ण निर्मेय मे अनेक पुनःस्थापन निम्न है। एक [[ट्यूरिंग मशीन|परिगणन यंत्र]] <math>M</math> दिया गया है, उस यंत्र x के लिए एक सहयोग, और एक नंबर T ([[यूनरी अंक प्रणाली|एकल अंक प्रणाली]]) में लिखा गया है, <math>\langle M,x,T \rangle</math> क्या वह यंत्र पहले T चरणों में उस सहयोग पर संवृत है? किसी भी X के लिए <math>L</math> p में परिगणन यंत्र के संकेतीकरण को उत्पादन करें जो इसे बहुपद-अवधि में स्वीकार करता है। x का संकेतीकरण और अनेक चरण <math>T=p(|x|)</math> जो p के अनुरूप जो परिगणन यंत्र के संचालन पर बहुपद-समयबद्ध है। <math>M_L</math> निर्णय लेने से <math>L</math>,<math>\langle M,x,p(|x|) \rangle</math> होगा। यंत्र M अंदर x पर रुकता है <math>p(|x|)</math> तो चरण यद्यपि और केवल यद्यपि x L में है। स्पष्ट रूप से यद्यपि हम अनुक्रमिक संगणक के सामान्य अनुकरण (अर्थात परिगणन यंत्र के परिगणन यंत्र अनुकरण ) को समानांतर कर सकते हैं तो हम उस संगणक पर चलने वाले किसी भी सभा को समानांतर करने में सक्षम होंगे। यदि यह निर्मेय NC में है, तो P में प्रत्येक दूसरी निर्मेय भी है। यदि द्विचर में चरणों की संख्या लिखी जाती है तो निर्मेय मे अपेक्षा अवधि-पूर्ण होती है। यह निर्मेय P-पूर्णता के सिद्धांत में एक सामान्य गति को दर्शाती है। हम वास्तव में इस बात में रूचि नहीं रखते हैं कि समानांतर यंत्र पर निर्मेय को शीघ्र से समाधित किया जा सकता है या नहीं। हम सिर्फ इस बात में रुचि रखते हैं कि क्या एक समानांतर यंत्र अनुक्रमिक यंत्र के अनुपात में इसे 'बहुत अधिक' शीघ्र से समाधित करता है। इसलिए हमें निर्मेय को फिर से लिखना होगा कि अनुक्रमिक संस्करण P में हो। यही कारण है कि इस निर्मेय को 'T' को एकल में लिखा जाना आवश्यक है। यदि एक संख्या T को एक द्विआधारी अंक प्रणाली संख्या (n वाले और शून्य की कङी, जहां n=संलेख T) के रूप में लिखा जाता है, तो स्पष्ट अनुक्रमिक कलन विधि मे 2<sup>n</sup> की अवधि लग सकती है। दूसरी ओर यदि T को एक एकल संख्या (n वाले की कङी, जहाँ n = T) के रूप में लिखा जाता है, तो इसमें केवल अवधि n लगती है। द्विचर के अतिरिक्त एकल में T लिखकर, हमने स्पष्ट अनुक्रमिक कलन विधि को घातीय अवधि से रैखिक अवधि तक कम कर दिया है। यह अनुक्रमिक निर्मेय को 'P' में रखता है। तत्पश्चात यह 'NC' में होगा और मात्र यद्यपि यह समांतर है।
यह समस्या पी-पूर्णता के सिद्धांत में एक सामान्य चाल को दर्शाती है। हम वास्तव में इस बात में दिलचस्पी नहीं रखते हैं कि समानांतर मशीन पर समस्या को जल्दी से हल किया जा सकता है या नहीं। हम सिर्फ इस बात में रुचि रखते हैं कि क्या एक समानांतर मशीन एक अनुक्रमिक मशीन की तुलना में इसे 'बहुत अधिक' तेजी से हल करती है। इसलिए, हमें समस्या को फिर से लिखना होगा ताकि अनुक्रमिक संस्करण पी में हो। यही कारण है कि इस समस्या को 'टी' को यूनरी में लिखा जाना आवश्यक है। यदि एक संख्या ''T'' को एक द्विआधारी अंक प्रणाली संख्या ("n'' वाले और शून्य की एक स्ट्रिंग, जहां ''n''= log ''T'') के रूप में लिखा जाता है, तो स्पष्ट अनुक्रमिक एल्गोरिदम कर सकते हैं समय लेना 2<sup>एन</sup>. दूसरी ओर, यदि T को एक एकल संख्या (n वाले की एक स्ट्रिंग, जहाँ n = T) के रूप में लिखा जाता है, तो इसमें केवल समय n लगता है। बाइनरी के बजाय यूनरी में टी लिखकर, हमने स्पष्ट अनुक्रमिक एल्गोरिदम को घातीय समय से रैखिक समय तक कम कर दिया है। यह अनुक्रमिक समस्या को 'पी' में रखता है। फिर, यह 'एनसी' में होगा अगर और केवल अगर यह समांतर है।


कई अन्य समस्याएं 'पी'-पूर्ण साबित हुई हैं, और इसलिए व्यापक रूप से स्वाभाविक अनुक्रमिक मानी जाती हैं। इनमें शामिल हैं
अनेक अन्य समस्याएं 'पी'-पूर्ण सिद्ध हुई हैं, और इसलिए व्यापक रूप से स्वाभाविक अनुक्रमिक मानी जाती हैं। इनमें निम्नलिखित समस्याएँ सम्मिलित हैं जो कम से कम अभिलेख अंतराल पुनःस्थापन के अंतर्गत 'पी'-पूर्ण हैं, जैसा कि दिया गया है, या निर्णय- निर्मेय के रूप में है''।''
निम्नलिखित समस्याएँ जो कम से कम लॉगस्पेस कटौती के तहत 'पी'-पूर्ण हैं, जैसा कि दिया गया है, या निर्णय-समस्या के रूप में:
* [[सर्किट वैल्यू प्रॉब्लम|परिपथ महत्व निर्मेय]] (सीवीपी) - एक [[Index.php?title= सर्किट|परिपथ]] दिया गया है। परिपथ में सहयोग और एक मार्ग है, उस मार्ग के उत्पादन की गणना करें।
* [[सर्किट वैल्यू प्रॉब्लम]] (CVP) - एक [[बूलियन सर्किट]] दिया गया है, सर्किट में इनपुट और सर्किट में एक गेट, उस गेट के आउटपुट की गणना करें।
* सीवीपी का प्रतिबंधित स्थिति - सीवीपी के सदृश प्रत्येक मार्ग को छोड़कर दो सहयोग और दो उत्पादन (F और रहित F) हैं, प्रत्येक दूसरी परत सिर्फ तथा मार्ग है, अन्य ओआर मार्ग हैं (या, समकक्ष, सभी मार्ग तथा पूरक मार्ग हैं, या सभी मार्ग एनओआर मार्ग हैं), एवं मार्ग के सहयोग तत्काल पूर्ववर्ती परत से आते हैं।
* सीवीपी का प्रतिबंधित मामला - सीवीपी की तरह, प्रत्येक गेट को छोड़कर दो इनपुट और दो आउटपुट (एफ और नॉट एफ) हैं, हर दूसरी परत सिर्फ AND गेट्स है, बाकी या गेट्स हैं (या, समकक्ष, सभी गेट्स नंद गेट्स हैं, या सभी द्वार NOR द्वार हैं), एक द्वार के इनपुट तुरंत पूर्ववर्ती परत से आते हैं
* [[रैखिक प्रोग्रामिंग|रैखिक कार्य रचना]] - रैखिक असमानता बाधाओं के अधीन एक रैखिक कार्य को अधिकतम करें।
* [[रैखिक प्रोग्रामिंग]] - रैखिक असमानता बाधाओं के अधीन एक रैखिक कार्य को अधिकतम करें
* कोशक्रमानुसार प्रथम मध्यमार्ग पहले खोज आदेश - निश्चित आदेशित आसन्न सूचियों ''एक [[ ग्राफ सिद्धांत |लेखाचित्र]] दिया गया है,'' और बिंदु u और v क्या शीर्ष u ने आसन्न सूचियों के क्रम से प्रेरित मध्यमार्ग-प्रथम खोज में शीर्ष v से पहले उपस्थिति किया है।
* लेक्सिकोग्राफिकली फर्स्ट डेप्थ फर्स्ट सर्च ऑर्डरिंग - फिक्स्ड ऑर्डरेड एडजेंसी लिस्ट और नोड्स यू और वी के साथ एक [[ ग्राफ सिद्धांत ]] को देखते हुए, क्या वर्टेक्स यू ने डेप्थ-फर्स्ट सर्च में वर्टेक्स वी से पहले विजिट किया है, जो आसन्न सूचियों के क्रम से प्रेरित है?
* [[संदर्भ मुक्त व्याकरण]] सदस्यता - एक संदर्भ मुक्त व्याकरण और एक कङी को देखते हुए। क्या वह कङी उस व्याकरण द्वारा उत्पन्न की जा सकती है?
* [[संदर्भ मुक्त व्याकरण]] सदस्यता - एक संदर्भ मुक्त व्याकरण और एक स्ट्रिंग को देखते हुए, क्या वह स्ट्रिंग उस व्याकरण द्वारा उत्पन्न की जा सकती है?
* [[हॉर्न-संतुष्टि]] - [[हॉर्न क्लॉज]] का एक समूह दिया गया है, क्या कोई परिवर्तनीय कार्य है जो उन्हें संतुष्ट करता है? यह [[बूलियन संतुष्टि समस्या|बूलियन संतुष्टि निर्मेय]] का पीएस संस्करण है।
* [[हॉर्न-संतुष्टि]] - [[हॉर्न क्लॉज]] का एक सेट दिया गया है, क्या कोई वैरिएबल असाइनमेंट है जो उन्हें संतुष्ट करता है? यह [[बूलियन संतुष्टि समस्या]] का Ps संस्करण है।
* चाल का जीवनकाल - कॉनवे के चाल का जीवनकाल के प्रारंभिक विन्यास को देखते हुए विशेष कक्ष, और एक अवधि T (एकल में) है, क्या वह कक्ष T चरणों के बाद सचेत है?
* गेम ऑफ लाइफ - कॉनवे के गेम ऑफ लाइफ के प्रारंभिक विन्यास को देखते हुए, एक विशेष सेल, और एक समय टी (यूनरी में), क्या वह सेल टी चरणों के बाद जीवित है?
* [[LZW (एल्गोरिदम)|एलजेडडब्लू (कलन विधि)]] (1978 प्रतिमान) आंकड़े संपीड़न - दिए गए कङी s और t एवं एलजेड78 विधि के साथ s को संपीड़ित करने से शब्दकोश में t जुड़ जाएगा? (ध्यान दें कि [[LZ77|एलजेड77]] संपीड़न जैसे कि [[gzip|जीज़िप]] के लिए यह बहुत आसान है, क्योंकि निर्मेय एस में T तक कम हो जाती है।)
* [[LZW (एल्गोरिदम)]] (1978 प्रतिमान) डेटा संपीड़न - दिए गए स्ट्रिंग्स s और t, LZ78 विधि के साथ s को संपीड़ित करने से शब्दकोश में t जुड़ जाएगा? (ध्यान दें कि [[LZ77]] संपीड़न जैसे कि [[gzip]] के लिए, यह बहुत आसान है, क्योंकि समस्या Is t in s? तक कम हो जाती है।)
* आंशिक प्रकार के लिए प्रकार का अनुमान - लैम्ब्डा गणना से एक [[प्रकार सिद्धांत|अप्रकाशित]] शब्द दिया गया है। यह निर्धारित करें कि इस शब्द का आंशिक प्रकार है या नहीं है।
* आंशिक प्रकार के लिए प्रकार का अनुमान - लैम्ब्डा कैलकुस से एक [[प्रकार सिद्धांत]] शब्द दिया गया है, यह निर्धारित करें कि इस शब्द का आंशिक प्रकार है या नहीं।


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


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


1999 में, जिन-यी कै और डी. शिवकुमार, ओगिहारा के काम पर निर्माण कर रहे थे, ने दिखाया कि अगर कोई [[विरल भाषा]] मौजूद है जो पी-पूर्ण है, तो एल = पी।<ref>{{Citation | last = Cai | first = Jin-Yi | last2 = Sivakumar | first2 = D. | title = Sparse hard sets for P: resolution of a conjecture of Hartmanis | journal = Journal of Computer and System Sciences | volume = 58 | issue = 2 | pages = 280&ndash;296 | year = 1999 | doi = 10.1006/jcss.1998.1615 | url = http://citeseer.ist.psu.edu/501645.html| doi-access = free }}</ref>
1999 में जिन-यी कै और डी. शिवकुमार ने ओगिहारा द्वारा कार्य पर कार्य, और उन्होंने दिखाया कि, यद्यपि कोई [[विरल भाषा]] उपस्थित है जो पी-पूर्ण है, तो L = P है।<ref>{{Citation | last = Cai | first = Jin-Yi | last2 = Sivakumar | first2 = D. | title = Sparse hard sets for P: resolution of a conjecture of Hartmanis | journal = Journal of Computer and System Sciences | volume = 58 | issue = 2 | pages = 280&ndash;296 | year = 1999 | doi = 10.1006/jcss.1998.1615 | url = http://citeseer.ist.psu.edu/501645.html| doi-access = free }}</ref> पी-पूर्ण समस्याएं अलग-अलग [[समय जटिलता|अवधि जटिलता]] के साथ समाधित करने योग्य हो सकती हैं। उदाहरण के लिए परिपथ महत्व निर्मेय को [[टोपोलॉजिकल सॉर्ट|संस्थानिक प्रकार]] द्वारा [[रैखिक समय|रैखिक अवधि]] में समाधित किया जा सकता है। निस्संदेह, क्योंकि पी-पूर्ण निर्मेय में पुनःस्थापन में अलग-अलग अवधि की जटिलताएं हो सकती हैं। इस तथ्य का अर्थ यह नहीं है कि P में सभी निर्मेयों को रैखिक अवधि में भी समाधित किया जा सकता है।
पी-पूर्ण समस्याएं अलग-अलग [[समय जटिलता]] के साथ हल करने योग्य हो सकती हैं। उदाहरण के लिए, सर्किट वैल्यू प्रॉब्लम को [[टोपोलॉजिकल सॉर्ट]] द्वारा [[रैखिक समय]] में हल किया जा सकता है। बेशक, क्योंकि पी-पूर्ण समस्या में कटौती में अलग-अलग समय की जटिलताएं हो सकती हैं, इस तथ्य का अर्थ यह नहीं है कि पी में सभी समस्याओं को रैखिक समय में भी हल किया जा सकता है।


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


कुछ एनपी-समस्याओं को या तो एनपी-पूर्ण या पी में नहीं जाना जाता है। इन समस्याओं (जैसे [[पूर्णांक गुणनखंडन]], [[ग्राफ समरूपता]], [[समता खेल]]) के कठिन होने का संदेह है{{Citation needed|date=October 2022}}. इसी तरह पी में ऐसी समस्याएं हैं जो या तो पी-पूर्ण या एनसी के रूप में नहीं जानी जाती हैं, लेकिन उन्हें समानांतर करना मुश्किल माना जाता है। उदाहरणों में दो संख्याओं का सबसे बड़ा सामान्य विभाजक खोजने के निर्णय समस्या रूप शामिल हैं, यह निर्धारित करना कि [[विस्तारित यूक्लिडियन एल्गोरिथ्म]] दो संख्याओं के दिए जाने पर क्या उत्तर देगा, और बड़े पूर्णांक भार वाले ग्राफ़ के अधिकतम भार मिलान की गणना करेगा।
कुछ NP- निर्मेयों को या तो NP-पूर्ण या P में नहीं माना जाता है। इन निर्मेयों (जैसे [[पूर्णांक गुणनखंडन]], [[ग्राफ समरूपता|लेखाचित्र समरूपता]], [[समता खेल]]) के कठिन होने का संदेह है। इसी तरह P में ऐसी समस्याएं हैं जो या तो P-पूर्ण या NC के रूप में नहीं जानी जाती हैं, किन्तु उन्हें समानांतर करना जटिल माना जाता है। उदाहरणों में दो संख्याओं का सबसे बड़ा सामान्य विभाजक निष्कर्ष के निर्णय निर्मेय रूप सम्मिलित हैं। यह निर्धारित करना कि [[विस्तारित यूक्लिडियन एल्गोरिथ्म|विस्तारित यूक्लिडियन कलन विधि]] दो संख्याओं के दिए जाने पर क्या उत्तर देगा, और बड़े पूर्णांक भार वाले लेखाचित्र के अधिकतम भार मिलान की गणना करेगा।


== टिप्पणियाँ ==
== टिप्पणियाँ ==
Line 58: Line 54:


{{ComplexityClasses}}
{{ComplexityClasses}}
[[Category: जटिलता वर्ग]]


 
[[Category:Collapse templates]]
 
[[Category: Machine Translated Page]]
[[Category:Created On 12/05/2023]]
[[Category:Created On 12/05/2023]]
[[Category:Machine Translated Page]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists]]
[[Category:Pages with script errors]]
[[Category:Sidebars with styles needing conversion]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates generating microformats]]
[[Category:Templates that are not mobile friendly]]
[[Category:Templates using TemplateData]]
[[Category:Wikipedia metatemplates]]
[[Category:जटिलता वर्ग]]

Latest revision as of 09:04, 15 June 2023

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

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

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

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

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

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

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

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

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

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

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

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

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

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

टिप्पणियाँ

  1. ↑ Cai, Jin-Yi; Sivakumar, D. (1999), "Sparse hard sets for P: resolution of a conjecture of Hartmanis", Journal of Computer and System Sciences, 58 (2): 280–296, doi:10.1006/jcss.1998.1615


संदर्भ

  • 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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=पी-पूर्ण&oldid=187712’