पी-पूर्ण: Difference between revisions
(Created page with "कम्प्यूटेशनल जटिलता सिद्धांत में, एक निर्णय समस्या जटिलता वर्...") |
No edit summary |
||
| Line 1: | Line 1: | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, एक [[निर्णय समस्या]] जटिलता वर्ग पी | [[कम्प्यूटेशनल जटिलता सिद्धांत|संगणनात्मक जटिलता सिद्धांत]] में, एक [[निर्णय समस्या]] पी-पूर्ण है (जटिलता वर्ग पी के लिए ([[पूर्ण (जटिलता)]]) है यदि यह पी में है और पी में हर समस्या उचित अभाव से [[कमी (जटिलता)|अभाव (जटिलता)]] हो सकती है। | ||
पी-पूर्ण निर्णय समस्याओं की धारणा विश्लेषण में उपयोगी है: | पी-पूर्ण निर्णय समस्याओं की धारणा विश्लेषण में उपयोगी है: | ||
* किन समस्याओं को प्रभावी ढंग से समानांतर करना | * किन समस्याओं को प्रभावी ढंग से समानांतर करना जटिल है, | ||
* सीमित स्थान में किन समस्याओं को | * सीमित स्थान में किन समस्याओं को समाधित करना जटिल है। | ||
विशेष रूप से जब | विशेष रूप से जब बहुअवधि- समानेयता की अनुपात में समानेयता की प्रबल धारणा पर विचार किया जाता है। | ||
उपयोग की जाने वाली विशिष्ट प्रकार की | उपयोग की जाने वाली विशिष्ट प्रकार की अभाव भिन्न होती है और समस्याओं के त्रुटिहीन समूह को प्रभावित कर सकती है। आम तौर पर, बहुपद-अवधि की पुनःस्थापन से प्रबल पुनःस्थापन का उपयोग किया जाता है, क्योंकि पी में सभी भाषाएं (रिक्त भाषा को छोड़कर और सभी कड़ियों की भाषा को छोड़कर) बहुपद-अवधि की अभाव के अंतर्गत पी-पूर्ण होती हैं। यदि हम एनसी (जटिलता) पुनःस्थापन का उपयोग करते हैं, अर्थात पुनःस्थापन जो संसाधक की बहुपद संख्या वाले समानांतर संगणक पर बहु लघुगणक अवधि में संचालित हो सकती है, तो सभी पी-पूर्ण समस्याएं एनसी के बाहर होती हैं और इसलिए अप्रमाणित धारणा के अंतर्गत प्रभावी रूप से समानांतर नहीं हो सकती हैं वह एनसी ≠ पी। यदि हम प्रबल [[लॉग-स्पेस कमी|अभिलेख -अंतराल अभाव]] का उपयोग करते हैं, तो यह सच रहता है, लेकिन इसके अतिरिक्त हम सीखते हैं कि सभी पी-पूर्ण समस्याएं कमजोर अप्रमाणित धारणा के अंतर्गत [[एल (जटिलता)]] के बाहर हैं। इस बाद के मामले में समूह पी-पूर्ण छोटा हो सकता है। | ||
== प्रेरणा == | == प्रेरणा == | ||
श्रेणी पी, आमतौर पर अनुक्रमिक संगणक के लिए सभी सरल समस्याओं को शामिल करने के लिए लिया जाता है, जिसमें श्रेणी एनसी शामिल होती है, जिसमें उन समस्याओं का समावेश होता है जिन्हें समांतर संगणक पर कुशलतापूर्वक समाधित किया जा सकता है। ऐसा इसलिए है क्योंकि समानांतर संगणकों को अनुक्रमिक यंत्र पर अनुकरण किया जा सकता है।यह ज्ञात नहीं है कि एनसी = पी। दूसरे शब्दों में, यह ज्ञात नहीं है कि क्या कोई सरल समस्याएं हैं जो स्वाभाविक रूप से अनुक्रमिक हैं। जिस तरह यह व्यापक रूप से संदेह है कि P, NP के बराबर नहीं है, उसी तरह व्यापक रूप से यह संदेह है कि NC, P के बराबर नहीं है। | |||
इसी तरह, | इसी तरह, श्रेणी एल (जटिलता) में वे सभी समस्याएं शामिल हैं जिन्हें लघुगणक अंतराल में अनुक्रमिक संगणक द्वारा समाधित किया जा सकता है। ऐसी यंत्रों बहुपद अवधि में चलती हैं क्योंकि उनके पास विन्यासों की बहुपद संख्या हो सकती है। ऐसा संदेह है कि 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> चरण यद्यपि और केवल यद्यपि एक्स एल में है। स्पष्ट रूप से, यद्यपि हम अनुक्रमिक संगणक के सामान्य अनुकरण (अर्थात परिगणन यंत्र के परिगणन यंत्र अनुकरण ) को समानांतर कर सकते हैं, तो हम उस संगणक पर चलने वाले किसी भी सभा को समानांतर करने में सक्षम होंगे . यदि यह समस्या एनसी में है, तो पी में हर दूसरी समस्या भी है। यदि द्विचर में चरणों की संख्या लिखी जाती है, तो समस्या अपेक्षा अवधि-पूर्ण होती है।यह समस्या पी-पूर्णता के सिद्धांत में एक सामान्य गति को दर्शाती है। हम वास्तव में इस बात में दिलचस्पी नहीं रखते हैं कि समानांतर यंत्र पर समस्या को शीघ्र से समाधित किया जा सकता है या नहीं। हम सिर्फ इस बात में रुचि रखते हैं कि क्या एक समानांतर यंत्र एक अनुक्रमिक यंत्र की अनुपात में इसे 'बहुत अधिक' शीघ्र से समाधित करती है। इसलिए, हमें समस्या को फिर से लिखना होगा कि अनुक्रमिक संस्करण पी में हो। यही कारण है कि इस समस्या को 'टी' को एकल में लिखा जाना आवश्यक है। यदि एक संख्या ''T'' को एक द्विआधारी अंक प्रणाली संख्या ("n'' वाले और शून्य की एक कङी, जहां ''n''= log ''T'') के रूप में लिखा जाता है, तो स्पष्ट अनुक्रमिक कलन विधि कर सकते हैं अवधि लेना 2<sup>n</sup>. दूसरी ओर, यदि T को एक एकल संख्या (n वाले की एक कङी, जहाँ n = T) के रूप में लिखा जाता है, तो इसमें केवल अवधि n लगता है। द्विचर के बजाय एकल में T लिखकर, हमने स्पष्ट अनुक्रमिक कलन विधि को घातीय अवधि से रैखिक अवधि तक कम कर दिया है। यह अनुक्रमिक समस्या को 'P' में रखता है। फिर, यह 'एनसी' में होगा यद्यपि और केवल यद्यपि यह समांतर है।'' | |||
अनेक अन्य समस्याएं 'पी'-पूर्ण साबित हुई हैं, और इसलिए व्यापक रूप से स्वाभाविक अनुक्रमिक मानी जाती हैं। इनमें शामिल हैं निम्नलिखित समस्याएँ जो कम से कम अभिलेख अंतराल पुनःस्थापन के अंतर्गत 'पी'-पूर्ण हैं, जैसा कि दिया गया है, या निर्णय-समस्या के रूप में: | |||
निम्नलिखित समस्याएँ जो कम से कम | * [[सर्किट वैल्यू प्रॉब्लम|सर्किट महत्व समस्या]] (सीवीपी) - एक [[Index.php?title= सर्किट|सर्किट]] दिया गया है, सर्किट में सहयोग और सर्किट में एक मार्ग, उस मार्ग के उत्पादन की गणना करें। | ||
* [[सर्किट वैल्यू प्रॉब्लम]] ( | * सीवीपी का प्रतिबंधित मामला - सीवीपी की तरह, प्रत्येक मार्ग को छोड़कर दो सहयोग और दो उत्पादन (एफ और रहित एफ) हैं, हर दूसरी परत सिर्फ और मार्ग है, स्थिरता या मार्ग हैं (या, समकक्ष, सभी मार्ग तथा पूरक मार्ग हैं, या सभी द्वार एनओआर द्वार हैं), एक द्वार के सहयोग तत्काल पूर्ववर्ती परत से आते हैं | ||
* सीवीपी का प्रतिबंधित मामला - सीवीपी की तरह, प्रत्येक | * [[रैखिक प्रोग्रामिंग|रैखिक कार्यरचना]] - रैखिक असमानता बाधाओं के अधीन एक रैखिक कार्य को अधिकतम करें | ||
* [[रैखिक प्रोग्रामिंग]] - रैखिक असमानता बाधाओं के अधीन एक रैखिक कार्य को अधिकतम करें | * कोशक्रमानुसार प्रथम मध्यमार्ग पहले खोज आदेश - निश्चित आदेशित आसन्न सूचियों और बिंदु यू और वी के साथ एक [[ ग्राफ सिद्धांत | लेखाचित्र सिद्धांत]] को देखते हुए, क्या शीर्ष यू ने मध्यमार्ग-प्रथम खोज में शीर्ष वी से पहले उपस्थिति किया है, जो आसन्न सूचियों के क्रम से प्रेरित है? | ||
* | * [[संदर्भ मुक्त व्याकरण]] सदस्यता - एक संदर्भ मुक्त व्याकरण और एक कङी को देखते हुए, क्या वह कङी उस व्याकरण द्वारा उत्पन्न की जा सकती है? | ||
* [[संदर्भ मुक्त व्याकरण]] सदस्यता - एक संदर्भ मुक्त व्याकरण और एक | * [[हॉर्न-संतुष्टि]] - [[हॉर्न क्लॉज]] का एक समूह दिया गया है, क्या कोई परिवर्तनीय कार्य है जो उन्हें संतुष्ट करता है? यह [[बूलियन संतुष्टि समस्या]] का Ps संस्करण है। | ||
* [[हॉर्न-संतुष्टि]] - [[हॉर्न क्लॉज]] का एक | * चाल का जीवनकाल - कॉनवे के चाल का जीवनकाल के प्रारंभिक विन्यास को देखते हुए, एक विशेष कक्ष, और एक अवधि टी (एकल में), क्या वह कक्ष टी चरणों के बाद सचेत है? | ||
* | * [[LZW (एल्गोरिदम)|एलजेडडब्लू (कलन विधि)]] (1978 प्रतिमान) आंकड़े संपीड़न - दिए गए कङी s और t, एलजेड78 विधि के साथ s को संपीड़ित करने से शब्दकोश में t जुड़ जाएगा? (ध्यान दें कि [[LZ77|एलजेड77]] संपीड़न जैसे कि [[gzip|जी ज़िप]] के लिए, यह बहुत आसान है, क्योंकि समस्या एस में टी है? तक कम हो जाती है।) | ||
* [[LZW (एल्गोरिदम)]] (1978 प्रतिमान) | * आंशिक प्रकार के लिए प्रकार का अनुमान - लैम्ब्डा गणना से एक [[प्रकार सिद्धांत]] शब्द दिया गया है, यह निर्धारित करें कि इस शब्द का आंशिक प्रकार है या नहीं। | ||
* आंशिक प्रकार के लिए प्रकार का अनुमान - लैम्ब्डा | |||
ऊपर दी गई अधिकांश भाषाएँ 'पी' हैं - | ऊपर दी गई अधिकांश भाषाएँ 'पी' हैं - अभाव की और भी प्रबल धारणाओं के अंतर्गत, जैसे कि वर्दी <math>AC^0</math> अनेक-एक पुनःस्थापन, DLOGTIME पुनःस्थापन, या बहुलघुगणकीय प्रक्षेपण। | ||
यह साबित करने के लिए कि पी में दी गई समस्या पी-पूर्ण है, आम तौर पर एक ज्ञात पी-पूर्ण समस्या को कम करने की कोशिश की जाती है। | यह साबित करने के लिए कि पी में दी गई समस्या पी-पूर्ण है, आम तौर पर एक ज्ञात पी-पूर्ण समस्या को कम करने की कोशिश की जाती है। | ||
1999 में, जिन-यी कै और डी. शिवकुमार, ओगिहारा के काम पर निर्माण कर रहे थे, ने दिखाया कि | 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–296 | year = 1999 | doi = 10.1006/jcss.1998.1615 | url = http://citeseer.ist.psu.edu/501645.html| doi-access = free }}</ref> | ||
पी-पूर्ण समस्याएं अलग-अलग [[समय जटिलता]] के साथ | पी-पूर्ण समस्याएं अलग-अलग [[समय जटिलता|अवधि जटिलता]] के साथ समाधित करने योग्य हो सकती हैं। उदाहरण के लिए, सर्किट महत्व समस्या को [[टोपोलॉजिकल सॉर्ट]] द्वारा [[रैखिक समय|रैखिक अवधि]] में समाधित किया जा सकता है। बेशक, क्योंकि पी-पूर्ण समस्या में पुनःस्थापन में अलग-अलग अवधि की जटिलताएं हो सकती हैं, इस तथ्य का अर्थ यह नहीं है कि पी में सभी समस्याओं को रैखिक अवधि में भी समाधित किया जा सकता है। | ||
== पी-पूर्ण == के रूप में ज्ञात समस्याएं नहीं | == पी-पूर्ण == के रूप में ज्ञात समस्याएं नहीं | ||
कुछ एनपी-समस्याओं को या तो एनपी-पूर्ण या पी में नहीं जाना जाता है। इन समस्याओं (जैसे [[पूर्णांक गुणनखंडन]], [[ग्राफ समरूपता]], [[समता खेल]]) के कठिन होने का संदेह है{{Citation needed|date=October 2022}}. इसी तरह पी में ऐसी समस्याएं हैं जो या तो पी-पूर्ण या एनसी के रूप में नहीं जानी जाती हैं, लेकिन उन्हें समानांतर करना | कुछ एनपी-समस्याओं को या तो एनपी-पूर्ण या पी में नहीं जाना जाता है। इन समस्याओं (जैसे [[पूर्णांक गुणनखंडन]], [[ग्राफ समरूपता|लेखाचित्र समरूपता]], [[समता खेल]]) के कठिन होने का संदेह है{{Citation needed|date=October 2022}}. इसी तरह पी में ऐसी समस्याएं हैं जो या तो पी-पूर्ण या एनसी के रूप में नहीं जानी जाती हैं, लेकिन उन्हें समानांतर करना जटिल माना जाता है। उदाहरणों में दो संख्याओं का सबसे बड़ा सामान्य विभाजक खोजने के निर्णय समस्या रूप शामिल हैं, यह निर्धारित करना कि [[विस्तारित यूक्लिडियन एल्गोरिथ्म]] दो संख्याओं के दिए जाने पर क्या उत्तर देगा, और बड़े पूर्णांक भार वाले ग्राफ़ के अधिकतम भार मिलान की गणना करेगा। | ||
== टिप्पणियाँ == | == टिप्पणियाँ == | ||
Revision as of 13:13, 17 May 2023
संगणनात्मक जटिलता सिद्धांत में, एक निर्णय समस्या पी-पूर्ण है (जटिलता वर्ग पी के लिए (पूर्ण (जटिलता)) है यदि यह पी में है और पी में हर समस्या उचित अभाव से अभाव (जटिलता) हो सकती है।
पी-पूर्ण निर्णय समस्याओं की धारणा विश्लेषण में उपयोगी है:
- किन समस्याओं को प्रभावी ढंग से समानांतर करना जटिल है,
- सीमित स्थान में किन समस्याओं को समाधित करना जटिल है।
विशेष रूप से जब बहुअवधि- समानेयता की अनुपात में समानेयता की प्रबल धारणा पर विचार किया जाता है।
उपयोग की जाने वाली विशिष्ट प्रकार की अभाव भिन्न होती है और समस्याओं के त्रुटिहीन समूह को प्रभावित कर सकती है। आम तौर पर, बहुपद-अवधि की पुनःस्थापन से प्रबल पुनःस्थापन का उपयोग किया जाता है, क्योंकि पी में सभी भाषाएं (रिक्त भाषा को छोड़कर और सभी कड़ियों की भाषा को छोड़कर) बहुपद-अवधि की अभाव के अंतर्गत पी-पूर्ण होती हैं। यदि हम एनसी (जटिलता) पुनःस्थापन का उपयोग करते हैं, अर्थात पुनःस्थापन जो संसाधक की बहुपद संख्या वाले समानांतर संगणक पर बहु लघुगणक अवधि में संचालित हो सकती है, तो सभी पी-पूर्ण समस्याएं एनसी के बाहर होती हैं और इसलिए अप्रमाणित धारणा के अंतर्गत प्रभावी रूप से समानांतर नहीं हो सकती हैं वह एनसी ≠ पी। यदि हम प्रबल अभिलेख -अंतराल अभाव का उपयोग करते हैं, तो यह सच रहता है, लेकिन इसके अतिरिक्त हम सीखते हैं कि सभी पी-पूर्ण समस्याएं कमजोर अप्रमाणित धारणा के अंतर्गत एल (जटिलता) के बाहर हैं। इस बाद के मामले में समूह पी-पूर्ण छोटा हो सकता है।
प्रेरणा
श्रेणी पी, आमतौर पर अनुक्रमिक संगणक के लिए सभी सरल समस्याओं को शामिल करने के लिए लिया जाता है, जिसमें श्रेणी एनसी शामिल होती है, जिसमें उन समस्याओं का समावेश होता है जिन्हें समांतर संगणक पर कुशलतापूर्वक समाधित किया जा सकता है। ऐसा इसलिए है क्योंकि समानांतर संगणकों को अनुक्रमिक यंत्र पर अनुकरण किया जा सकता है।यह ज्ञात नहीं है कि एनसी = पी। दूसरे शब्दों में, यह ज्ञात नहीं है कि क्या कोई सरल समस्याएं हैं जो स्वाभाविक रूप से अनुक्रमिक हैं। जिस तरह यह व्यापक रूप से संदेह है कि P, NP के बराबर नहीं है, उसी तरह व्यापक रूप से यह संदेह है कि NC, P के बराबर नहीं है।
इसी तरह, श्रेणी एल (जटिलता) में वे सभी समस्याएं शामिल हैं जिन्हें लघुगणक अंतराल में अनुक्रमिक संगणक द्वारा समाधित किया जा सकता है। ऐसी यंत्रों बहुपद अवधि में चलती हैं क्योंकि उनके पास विन्यासों की बहुपद संख्या हो सकती है। ऐसा संदेह है कि L ≠ P; अर्थात्, कुछ समस्याएँ जिन्हें बहुपद अवधि में समाधित किया जा सकता है, उन्हें भी लघुगणक स्थान से अधिक की आवश्यकता होती है।
इसी तरह पी = एनपी संदेह का विश्लेषण करने के लिए एनपी-पूर्ण समस्याओं के उपयोग के लिए, पी-पूर्ण समस्याओं को संभवतः समानांतर नहीं या संभवतः अंतर्निहित अनुक्रमिक समस्याओं के रूप में देखा जाता है, इसी तरह से एनसी = पी संदेह का अध्ययन करने के लिए कार्य करता है। कुछ पी-पूर्ण समस्या के समाधान को समानांतर करने का एक कुशल तरीका खोजने से पता चलेगा कि एनसी = पी। इसे उत्तम लघुगणक अंतराल की आवश्यकता वाली समस्याओं के रूप में भी सोचा जा सकता है; पी-पूर्ण समस्या के लिए एक अभिलेख -अंतराल समाधान (अभिलेख -अंतराल पुनःस्थापन के आधार पर परिभाषा का उपयोग करके) एल = पी का अर्थ होगा।
इसके पीछे तर्क तर्क के समान है कि एक एनपी-पूर्ण समस्या का बहुपद-अवधि समाधान पी = एनपी साबित होगा: यदि हमारे पास पी में किसी भी समस्या से एक समस्या ए में एनसी अभाव है, और ए के लिए एक एनसी समाधान है, तो एनसी = पी। इसी प्रकार, यदि हमारे पास पी में किसी समस्या से समस्या ए में अभिलेख -अंतराल अभाव है, और ए के लिए अभिलेख -अंतराल समाधान है, तो एल = पी।
पी-पूर्ण समस्याएं
अभिलेख अंतराल के अंतर्गत सबसे मूलभूत पी-पूर्ण समस्या अनेक-एक पुनःस्थापन निम्न है: एक परिगणन यंत्र दी गई है , उस यंत्र x के लिए एक सहयोग, और एक नंबर T (एकल अंक प्रणाली में लिखा गया), क्या वह यंत्र पहले टी चरणों में उस सहयोग पर संवृत है? किसी भी एक्स के लिए पी में, परिगणन यंत्र के संकेतीकरण को उत्पादन करें जो इसे बहुपद-अवधि में स्वीकार करता है, एक्स का संकेतीकरण और अनेक चरण पी के अनुरूप जो परिगणन यंत्र के संचालन पर बहुपद-समयबद्ध है निर्णय लेने से , . यंत्र M अंदर x पर संवृत है चरण यद्यपि और केवल यद्यपि एक्स एल में है। स्पष्ट रूप से, यद्यपि हम अनुक्रमिक संगणक के सामान्य अनुकरण (अर्थात परिगणन यंत्र के परिगणन यंत्र अनुकरण ) को समानांतर कर सकते हैं, तो हम उस संगणक पर चलने वाले किसी भी सभा को समानांतर करने में सक्षम होंगे . यदि यह समस्या एनसी में है, तो पी में हर दूसरी समस्या भी है। यदि द्विचर में चरणों की संख्या लिखी जाती है, तो समस्या अपेक्षा अवधि-पूर्ण होती है।यह समस्या पी-पूर्णता के सिद्धांत में एक सामान्य गति को दर्शाती है। हम वास्तव में इस बात में दिलचस्पी नहीं रखते हैं कि समानांतर यंत्र पर समस्या को शीघ्र से समाधित किया जा सकता है या नहीं। हम सिर्फ इस बात में रुचि रखते हैं कि क्या एक समानांतर यंत्र एक अनुक्रमिक यंत्र की अनुपात में इसे 'बहुत अधिक' शीघ्र से समाधित करती है। इसलिए, हमें समस्या को फिर से लिखना होगा कि अनुक्रमिक संस्करण पी में हो। यही कारण है कि इस समस्या को 'टी' को एकल में लिखा जाना आवश्यक है। यदि एक संख्या T को एक द्विआधारी अंक प्रणाली संख्या ("n वाले और शून्य की एक कङी, जहां n= log T) के रूप में लिखा जाता है, तो स्पष्ट अनुक्रमिक कलन विधि कर सकते हैं अवधि लेना 2n. दूसरी ओर, यदि T को एक एकल संख्या (n वाले की एक कङी, जहाँ n = T) के रूप में लिखा जाता है, तो इसमें केवल अवधि n लगता है। द्विचर के बजाय एकल में T लिखकर, हमने स्पष्ट अनुक्रमिक कलन विधि को घातीय अवधि से रैखिक अवधि तक कम कर दिया है। यह अनुक्रमिक समस्या को 'P' में रखता है। फिर, यह 'एनसी' में होगा यद्यपि और केवल यद्यपि यह समांतर है।
अनेक अन्य समस्याएं 'पी'-पूर्ण साबित हुई हैं, और इसलिए व्यापक रूप से स्वाभाविक अनुक्रमिक मानी जाती हैं। इनमें शामिल हैं निम्नलिखित समस्याएँ जो कम से कम अभिलेख अंतराल पुनःस्थापन के अंतर्गत 'पी'-पूर्ण हैं, जैसा कि दिया गया है, या निर्णय-समस्या के रूप में:
- सर्किट महत्व समस्या (सीवीपी) - एक सर्किट दिया गया है, सर्किट में सहयोग और सर्किट में एक मार्ग, उस मार्ग के उत्पादन की गणना करें।
- सीवीपी का प्रतिबंधित मामला - सीवीपी की तरह, प्रत्येक मार्ग को छोड़कर दो सहयोग और दो उत्पादन (एफ और रहित एफ) हैं, हर दूसरी परत सिर्फ और मार्ग है, स्थिरता या मार्ग हैं (या, समकक्ष, सभी मार्ग तथा पूरक मार्ग हैं, या सभी द्वार एनओआर द्वार हैं), एक द्वार के सहयोग तत्काल पूर्ववर्ती परत से आते हैं
- रैखिक कार्यरचना - रैखिक असमानता बाधाओं के अधीन एक रैखिक कार्य को अधिकतम करें
- कोशक्रमानुसार प्रथम मध्यमार्ग पहले खोज आदेश - निश्चित आदेशित आसन्न सूचियों और बिंदु यू और वी के साथ एक लेखाचित्र सिद्धांत को देखते हुए, क्या शीर्ष यू ने मध्यमार्ग-प्रथम खोज में शीर्ष वी से पहले उपस्थिति किया है, जो आसन्न सूचियों के क्रम से प्रेरित है?
- संदर्भ मुक्त व्याकरण सदस्यता - एक संदर्भ मुक्त व्याकरण और एक कङी को देखते हुए, क्या वह कङी उस व्याकरण द्वारा उत्पन्न की जा सकती है?
- हॉर्न-संतुष्टि - हॉर्न क्लॉज का एक समूह दिया गया है, क्या कोई परिवर्तनीय कार्य है जो उन्हें संतुष्ट करता है? यह बूलियन संतुष्टि समस्या का Ps संस्करण है।
- चाल का जीवनकाल - कॉनवे के चाल का जीवनकाल के प्रारंभिक विन्यास को देखते हुए, एक विशेष कक्ष, और एक अवधि टी (एकल में), क्या वह कक्ष टी चरणों के बाद सचेत है?
- एलजेडडब्लू (कलन विधि) (1978 प्रतिमान) आंकड़े संपीड़न - दिए गए कङी s और t, एलजेड78 विधि के साथ s को संपीड़ित करने से शब्दकोश में t जुड़ जाएगा? (ध्यान दें कि एलजेड77 संपीड़न जैसे कि जी ज़िप के लिए, यह बहुत आसान है, क्योंकि समस्या एस में टी है? तक कम हो जाती है।)
- आंशिक प्रकार के लिए प्रकार का अनुमान - लैम्ब्डा गणना से एक प्रकार सिद्धांत शब्द दिया गया है, यह निर्धारित करें कि इस शब्द का आंशिक प्रकार है या नहीं।
ऊपर दी गई अधिकांश भाषाएँ 'पी' हैं - अभाव की और भी प्रबल धारणाओं के अंतर्गत, जैसे कि वर्दी अनेक-एक पुनःस्थापन, DLOGTIME पुनःस्थापन, या बहुलघुगणकीय प्रक्षेपण।
यह साबित करने के लिए कि पी में दी गई समस्या पी-पूर्ण है, आम तौर पर एक ज्ञात पी-पूर्ण समस्या को कम करने की कोशिश की जाती है।
1999 में, जिन-यी कै और डी. शिवकुमार, ओगिहारा के काम पर निर्माण कर रहे थे, ने दिखाया कि यद्यपि कोई विरल भाषा मौजूद है जो पी-पूर्ण है, तो एल = पी।[1] पी-पूर्ण समस्याएं अलग-अलग अवधि जटिलता के साथ समाधित करने योग्य हो सकती हैं। उदाहरण के लिए, सर्किट महत्व समस्या को टोपोलॉजिकल सॉर्ट द्वारा रैखिक अवधि में समाधित किया जा सकता है। बेशक, क्योंकि पी-पूर्ण समस्या में पुनःस्थापन में अलग-अलग अवधि की जटिलताएं हो सकती हैं, इस तथ्य का अर्थ यह नहीं है कि पी में सभी समस्याओं को रैखिक अवधि में भी समाधित किया जा सकता है।
== पी-पूर्ण == के रूप में ज्ञात समस्याएं नहीं
कुछ एनपी-समस्याओं को या तो एनपी-पूर्ण या पी में नहीं जाना जाता है। इन समस्याओं (जैसे पूर्णांक गुणनखंडन, लेखाचित्र समरूपता, समता खेल) के कठिन होने का संदेह है[citation needed]. इसी तरह पी में ऐसी समस्याएं हैं जो या तो पी-पूर्ण या एनसी के रूप में नहीं जानी जाती हैं, लेकिन उन्हें समानांतर करना जटिल माना जाता है। उदाहरणों में दो संख्याओं का सबसे बड़ा सामान्य विभाजक खोजने के निर्णय समस्या रूप शामिल हैं, यह निर्धारित करना कि विस्तारित यूक्लिडियन एल्गोरिथ्म दो संख्याओं के दिए जाने पर क्या उत्तर देगा, और बड़े पूर्णांक भार वाले ग्राफ़ के अधिकतम भार मिलान की गणना करेगा।
टिप्पणियाँ
- ↑ 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.
