♯पी-पूर्ण: Difference between revisions
From Vigyanwiki
(Created page with "{{short description|Complexity class}} {{correct title|#P-complete|reason=#}} कम्प्यूटेशनल जटिलता सिद्धांत में #...") |
No edit summary |
||
| Line 2: | Line 2: | ||
{{correct title|#P-complete|reason=#}} | {{correct title|#P-complete|reason=#}} | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में #पी-पूर्ण समस्याएं (उच्चारण | [[कम्प्यूटेशनल जटिलता सिद्धांत]] में #पी-पूर्ण समस्याएं (उच्चारण प्रखरपी पूर्ण या संख्या पी पूर्ण) एक [[जटिलता वर्ग]] बनाती हैं। इस जटिलता वर्ग की समस्याओं को निम्नलिखित दो गुण होने से परिभाषित किया गया है: | ||
*समस्या ♯P | *समस्या ♯P में है, समस्याओं का वर्ग जिसे एक बहुपद-समय [[गैर-नियतात्मक ट्यूरिंग मशीन]] के स्वीकृत पथों की संख्या की गणना के रूप में परिभाषित किया जा सकता है। | ||
*समस्या ♯P | *समस्या ♯P -कठोर है, जिसका अर्थ है कि #P में हर दूसरी समस्या में [[ ट्यूरिंग कमी ]] या [[बहुपद-समय की गिनती में कमी]] है। एक गिनती में कमी दूसरी समस्या के इनपुट से दी गई समस्या के इनपुट और दी गई समस्या के आउटपुट से दूसरी समस्या के आउटपुट तक बहुपद-समय के परिवर्तनों की एक जोड़ी है, जो दी गई समस्या के लिए किसी भी प्रक्रिया का उपयोग करके अन्य समस्या को हल करने की अनुमति देती है। एक ट्यूरिंग अपचयन दूसरी समस्या के लिए एक एल्गोरिथ्म है जो दी गई समस्या के लिए एक प्रक्रिया को बहुपद संख्या में आदेश करता है और उन आदेश के बाहर, [[बहुपदी समय फलन]] उपयोग करता है। कुछ कारको में पारसीमोनियस अपचयन, एक अधिक विशिष्ट प्रकार की कमी जो समाधानों की सटीक संख्या को संरक्षित करती है, का उपयोग किया जाता है। | ||
<nowiki># | <nowiki>#</nowiki>P-पूर्ण समस्याएँ कम से कम उतनी ही कठिन हैं जितनी कि NP-पूर्ण समस्याएँ।<ref>{{cite journal |last1=Valiant |first1=Leslie G. |title=गणना और विश्वसनीयता की समस्याओं की जटिलता|journal=SIAM Journal on Computing |date=August 1979 |volume=8 |issue=3 |pages=410–421 |doi=10.1137/0208032 |url=https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf}}</ref> #P-पूर्ण समस्या को हल करने के लिए एक बहुपद-समय एल्गोरिथ्म, यदि यह अस्तित्व में है, तो P विरुद्ध NP समस्या को P और NP के बराबर होने का अर्थ देकर हल करेगा। ऐसा कोई एल्गोरिथम ज्ञात नहीं है, न ही ऐसा कोई प्रमाण ज्ञात है कि ऐसा एल्गोरिथम उपस्थित नहीं है। | ||
== उदाहरण == | == उदाहरण == | ||
#P-पूर्ण समस्याओं के उदाहरणों में | #P-पूर्ण समस्याओं के उदाहरणों में सम्मिलित हैं: | ||
* कितने भिन्न चर नियतन दिए गए सामान्य बूलियन सूत्र को संतुष्ट करेंगे? ( | * कितने भिन्न चर नियतन दिए गए सामान्य बूलियन सूत्र को संतुष्ट करेंगे? (#SAT) | ||
* कितने अलग-अलग | * कितने अलग-अलग चर नियतन दिए गए [[असंबद्ध सामान्य रूप]] फॉर्मूले को संतुष्ट करेंगे? | ||
* दी गई 2-संतोषजनक समस्या को कितने अलग-अलग चर | * दी गई 2-संतोषजनक समस्या को कितने अलग-अलग चर नियतन संतुष्ट करेंगे? | ||
* दिए गए द्विदलीय ग्राफ के लिए कितने पूर्ण मिलान हैं? | * दिए गए द्विदलीय ग्राफ के लिए कितने पूर्ण मिलान हैं? | ||
* किसी दिए गए मैट्रिक्स के [[स्थायी (गणित)]] का मान क्या है जिसकी प्रविष्टियाँ 0 या 1 हैं? (देखें | * किसी दिए गए मैट्रिक्स के [[स्थायी (गणित)]] का मान क्या है जिसकी प्रविष्टियाँ 0 या 1 हैं? (देखें #पी-01-स्थायी की पूर्णता।) | ||
* किसी विशेष ग्राफ़ G के लिए k रंगों का उपयोग करने वाले कितने [[ग्राफ रंग]] हैं? | * किसी विशेष ग्राफ़ G के लिए k रंगों का उपयोग करने वाले कितने [[ग्राफ रंग]] हैं? | ||
* दिए गए आंशिक रूप से ऑर्डर किए गए सेट के लिए कितने अलग रैखिक | * दिए गए आंशिक रूप से ऑर्डर किए गए सेट के लिए कितने अलग रैखिक विस्तारण हैं, या समतुल्य, दिए गए एसाइक्लिक ग्राफ के लिए कितने अलग-अलग [[ टोपोलॉजिकल छँटाई ]] हैं?<ref>{{Cite journal | ||
| last1 = Brightwell | first1 = Graham R. | | last1 = Brightwell | first1 = Graham R. | ||
| last2 = Winkler | first2 = Peter | author2-link = Peter Winkler | | last2 = Winkler | first2 = Peter | author2-link = Peter Winkler | ||
| Line 30: | Line 30: | ||
ये सभी आवश्यक रूप से कक्षा ♯P|#P के भी सदस्य हैं। एक गैर-उदाहरण के रूप में, 1-संतोषजनक समस्या के समाधान की गिनती के मामले पर विचार करें: वेरिएबल्स की एक श्रृंखला जो प्रत्येक व्यक्तिगत रूप से विवश हैं, लेकिन एक दूसरे के साथ कोई संबंध नहीं है। अलगाव में प्रत्येक चर के लिए विकल्पों की संख्या को गुणा करके समाधानों को कुशलतापूर्वक गिना जा सकता है। इस प्रकार, यह समस्या ♯P|#P में है, लेकिन #P-पूर्ण नहीं हो सकती जब तक ♯P|#P=FP (जटिलता)। यह आश्चर्यजनक होगा, क्योंकि इसका अर्थ यह होगा कि P (जटिलता) = NP (जटिलता) = PH (जटिलता)। | ये सभी आवश्यक रूप से कक्षा ♯P|#P के भी सदस्य हैं। एक गैर-उदाहरण के रूप में, 1-संतोषजनक समस्या के समाधान की गिनती के मामले पर विचार करें: वेरिएबल्स की एक श्रृंखला जो प्रत्येक व्यक्तिगत रूप से विवश हैं, लेकिन एक दूसरे के साथ कोई संबंध नहीं है। अलगाव में प्रत्येक चर के लिए विकल्पों की संख्या को गुणा करके समाधानों को कुशलतापूर्वक गिना जा सकता है। इस प्रकार, यह समस्या ♯P|#P में है, लेकिन #P-पूर्ण नहीं हो सकती जब तक ♯P|#P=FP (जटिलता)। यह आश्चर्यजनक होगा, क्योंकि इसका अर्थ यह होगा कि P (जटिलता) = NP (जटिलता) = PH (जटिलता)। | ||
== | == कठोर काउंटिंग वर्जन के साथ आसान समस्याएं == | ||
कुछ #P-पूर्ण समस्याएं आसान (P (जटिलता)) समस्याओं के अनुरूप होती हैं। डीएनएफ में एक बूलियन फॉर्मूला की संतुष्टि का निर्धारण करना आसान है: ऐसा फॉर्मूला संतोषजनक है अगर और केवल अगर इसमें एक संतोषजनक संयोजन होता है (जिसमें एक चर और इसकी अस्वीकृति नहीं होती है), जबकि संतोषजनक | कुछ #P-पूर्ण समस्याएं आसान (P (जटिलता)) समस्याओं के अनुरूप होती हैं। डीएनएफ में एक बूलियन फॉर्मूला की संतुष्टि का निर्धारण करना आसान है: ऐसा फॉर्मूला संतोषजनक है अगर और केवल अगर इसमें एक संतोषजनक संयोजन होता है (जिसमें एक चर और इसकी अस्वीकृति नहीं होती है), जबकि संतोषजनक नियतन की संख्या की गणना करना #P- है पूरा। इसके अलावा, संतोषजनक कार्यों की संख्या की गणना करने की तुलना में 2-संतोषजनकता तय करना आसान है। टोपोलॉजिकल सॉर्टिंग की संख्या गिनने के विपरीत टोपोलॉजिकल सॉर्टिंग आसान है। एक एकल मिलान (ग्राफ़ सिद्धांत) बहुपद समय में पाया जा सकता है, लेकिन सभी पूर्ण मिलानों की गणना करना #P-पूर्ण है। 1979 में [[लेस्ली बहादुर]] के एक पेपर में सटीक मिलान वाली गिनती की समस्या एक आसान पी समस्या के अनुरूप पहली गिनती की समस्या थी, जिसे #P-पूर्ण दिखाया गया था, जिसमें पहली बार कक्षा #P और #P-पूर्ण समस्याओं को भी परिभाषित किया गया था।<ref>{{cite journal | ||
| author = Leslie G. Valiant | | author = Leslie G. Valiant | ||
| title = The Complexity of Computing the Permanent | | title = The Complexity of Computing the Permanent | ||
Revision as of 13:43, 19 May 2023
कम्प्यूटेशनल जटिलता सिद्धांत में #पी-पूर्ण समस्याएं (उच्चारण प्रखरपी पूर्ण या संख्या पी पूर्ण) एक जटिलता वर्ग बनाती हैं। इस जटिलता वर्ग की समस्याओं को निम्नलिखित दो गुण होने से परिभाषित किया गया है:
- समस्या ♯P में है, समस्याओं का वर्ग जिसे एक बहुपद-समय गैर-नियतात्मक ट्यूरिंग मशीन के स्वीकृत पथों की संख्या की गणना के रूप में परिभाषित किया जा सकता है।
- समस्या ♯P -कठोर है, जिसका अर्थ है कि #P में हर दूसरी समस्या में ट्यूरिंग कमी या बहुपद-समय की गिनती में कमी है। एक गिनती में कमी दूसरी समस्या के इनपुट से दी गई समस्या के इनपुट और दी गई समस्या के आउटपुट से दूसरी समस्या के आउटपुट तक बहुपद-समय के परिवर्तनों की एक जोड़ी है, जो दी गई समस्या के लिए किसी भी प्रक्रिया का उपयोग करके अन्य समस्या को हल करने की अनुमति देती है। एक ट्यूरिंग अपचयन दूसरी समस्या के लिए एक एल्गोरिथ्म है जो दी गई समस्या के लिए एक प्रक्रिया को बहुपद संख्या में आदेश करता है और उन आदेश के बाहर, बहुपदी समय फलन उपयोग करता है। कुछ कारको में पारसीमोनियस अपचयन, एक अधिक विशिष्ट प्रकार की कमी जो समाधानों की सटीक संख्या को संरक्षित करती है, का उपयोग किया जाता है।
#P-पूर्ण समस्याएँ कम से कम उतनी ही कठिन हैं जितनी कि NP-पूर्ण समस्याएँ।[1] #P-पूर्ण समस्या को हल करने के लिए एक बहुपद-समय एल्गोरिथ्म, यदि यह अस्तित्व में है, तो P विरुद्ध NP समस्या को P और NP के बराबर होने का अर्थ देकर हल करेगा। ऐसा कोई एल्गोरिथम ज्ञात नहीं है, न ही ऐसा कोई प्रमाण ज्ञात है कि ऐसा एल्गोरिथम उपस्थित नहीं है।
उदाहरण
- P-पूर्ण समस्याओं के उदाहरणों में सम्मिलित हैं:
- कितने भिन्न चर नियतन दिए गए सामान्य बूलियन सूत्र को संतुष्ट करेंगे? (#SAT)
- कितने अलग-अलग चर नियतन दिए गए असंबद्ध सामान्य रूप फॉर्मूले को संतुष्ट करेंगे?
- दी गई 2-संतोषजनक समस्या को कितने अलग-अलग चर नियतन संतुष्ट करेंगे?
- दिए गए द्विदलीय ग्राफ के लिए कितने पूर्ण मिलान हैं?
- किसी दिए गए मैट्रिक्स के स्थायी (गणित) का मान क्या है जिसकी प्रविष्टियाँ 0 या 1 हैं? (देखें #पी-01-स्थायी की पूर्णता।)
- किसी विशेष ग्राफ़ G के लिए k रंगों का उपयोग करने वाले कितने ग्राफ रंग हैं?
- दिए गए आंशिक रूप से ऑर्डर किए गए सेट के लिए कितने अलग रैखिक विस्तारण हैं, या समतुल्य, दिए गए एसाइक्लिक ग्राफ के लिए कितने अलग-अलग टोपोलॉजिकल छँटाई हैं?[2]
ये सभी आवश्यक रूप से कक्षा ♯P|#P के भी सदस्य हैं। एक गैर-उदाहरण के रूप में, 1-संतोषजनक समस्या के समाधान की गिनती के मामले पर विचार करें: वेरिएबल्स की एक श्रृंखला जो प्रत्येक व्यक्तिगत रूप से विवश हैं, लेकिन एक दूसरे के साथ कोई संबंध नहीं है। अलगाव में प्रत्येक चर के लिए विकल्पों की संख्या को गुणा करके समाधानों को कुशलतापूर्वक गिना जा सकता है। इस प्रकार, यह समस्या ♯P|#P में है, लेकिन #P-पूर्ण नहीं हो सकती जब तक ♯P|#P=FP (जटिलता)। यह आश्चर्यजनक होगा, क्योंकि इसका अर्थ यह होगा कि P (जटिलता) = NP (जटिलता) = PH (जटिलता)।
कठोर काउंटिंग वर्जन के साथ आसान समस्याएं
कुछ #P-पूर्ण समस्याएं आसान (P (जटिलता)) समस्याओं के अनुरूप होती हैं। डीएनएफ में एक बूलियन फॉर्मूला की संतुष्टि का निर्धारण करना आसान है: ऐसा फॉर्मूला संतोषजनक है अगर और केवल अगर इसमें एक संतोषजनक संयोजन होता है (जिसमें एक चर और इसकी अस्वीकृति नहीं होती है), जबकि संतोषजनक नियतन की संख्या की गणना करना #P- है पूरा। इसके अलावा, संतोषजनक कार्यों की संख्या की गणना करने की तुलना में 2-संतोषजनकता तय करना आसान है। टोपोलॉजिकल सॉर्टिंग की संख्या गिनने के विपरीत टोपोलॉजिकल सॉर्टिंग आसान है। एक एकल मिलान (ग्राफ़ सिद्धांत) बहुपद समय में पाया जा सकता है, लेकिन सभी पूर्ण मिलानों की गणना करना #P-पूर्ण है। 1979 में लेस्ली बहादुर के एक पेपर में सटीक मिलान वाली गिनती की समस्या एक आसान पी समस्या के अनुरूप पहली गिनती की समस्या थी, जिसे #P-पूर्ण दिखाया गया था, जिसमें पहली बार कक्षा #P और #P-पूर्ण समस्याओं को भी परिभाषित किया गया था।[3]
सन्निकटन
संभाव्य एल्गोरिदम हैं जो उच्च संभावना के साथ कुछ # पी-पूर्ण समस्याओं के लिए अच्छा अनुमान लगाते हैं। यह संभाव्य एल्गोरिदम की शक्ति के प्रदर्शनों में से एक है।
कई #P-पूर्ण समस्याओं में एक बहुपद-समय सन्निकटन योजना है। पूर्ण बहुपद-समय यादृच्छिक सन्निकटन योजना, या FPRAS, जो, अनौपचारिक रूप से, उच्च संभाव्यता के साथ सटीकता की एक मनमाना डिग्री के सन्निकटन का उत्पादन करेगी, जो समय के साथ बहुपद है समस्या के आकार और आवश्यक सटीकता की डिग्री दोनों के लिए। मार्क जेरम, लेस्ली वैलिएंट, और विजय वजीरानी ने दिखाया कि हर #P-पूर्ण समस्या में या तो एक FPRAS होता है, या अनुमानित रूप से असंभव है; यदि कोई बहुपद-समय एल्गोरिदम है जो लगातार एक #P-पूर्ण समस्या का अनुमान लगाता है जो सटीक उत्तर के इनपुट के आकार में बहुपद अनुपात के भीतर है, तो उस एल्गोरिदम का उपयोग FPRAS के निर्माण के लिए किया जा सकता है।[4]
संदर्भ
- ↑ Valiant, Leslie G. (August 1979). "गणना और विश्वसनीयता की समस्याओं की जटिलता" (PDF). SIAM Journal on Computing. 8 (3): 410–421. doi:10.1137/0208032.
- ↑ Brightwell, Graham R.; Winkler, Peter (1991). "Counting linear extensions". Order. 8 (3): 225–242. doi:10.1007/BF00383444. S2CID 119697949..
- ↑ Leslie G. Valiant (1979). "The Complexity of Computing the Permanent". Theoretical Computer Science. Elsevier. 8 (2): 189–201. doi:10.1016/0304-3975(79)90044-6.
- ↑ Mark R. Jerrum; Leslie G. Valiant; Vijay V. Vazirani (1986). "Random Generation of Combinatorial Structures from a Uniform Distribution". Theoretical Computer Science. Elsevier. 43: 169–188. doi:10.1016/0304-3975(86)90174-x.
अग्रिम पठन
- Vazirani, Vijay V. (2003). Approximation Algorithms. Berlin: Springer. ISBN 3-540-65367-8.
