♯पी-पूर्ण: Difference between revisions
No edit summary |
No edit summary |
||
| Line 16: | Line 16: | ||
* किसी दिए गए मैट्रिक्स के [[स्थायी (गणित)]] का मान क्या है जिसकी प्रविष्टियाँ 0 या 1 हैं? (देखें #पी-01-स्थायी की पूर्णता।) | * किसी दिए गए मैट्रिक्स के [[स्थायी (गणित)]] का मान क्या है जिसकी प्रविष्टियाँ 0 या 1 हैं? (देखें #पी-01-स्थायी की पूर्णता।) | ||
* किसी विशेष ग्राफ़ G के लिए k रंगों का उपयोग करने वाले कितने [[ग्राफ रंग]] हैं? | * किसी विशेष ग्राफ़ G के लिए k रंगों का उपयोग करने वाले कितने [[ग्राफ रंग]] हैं? | ||
* दिए गए आंशिक रूप से | * दिए गए आंशिक रूप से क्रमित किए गए सेट के लिए कितने अलग रैखिक विस्तारण हैं, या समतुल्य, दिए गए एसाइक्लिक ग्राफ के लिए कितने अलग-अलग [[Index.php?title=टोपोलॉजिकल क्रम|टोपोलॉजिकल क्रम]] हैं?<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 28: | Line 28: | ||
| s2cid = 119697949 | | s2cid = 119697949 | ||
}}.</ref> | }}.</ref> | ||
ये सभी आवश्यक रूप से कक्षा ♯P | ये सभी आवश्यक रूप से कक्षा ♯P के भी सदस्य हैं। एक गैर-उदाहरण के रूप में, 1-संतोषजनक समस्या के समाधान की गिनती के मामले पर विचार करें: चर राशि की एक श्रृंखला जो प्रत्येक व्यक्तिगत रूप से विवश हैं, लेकिन एक दूसरे के साथ कोई संबंध नहीं है। विलगन में प्रत्येक चर के लिए विकल्पों की संख्या को गुणा करके समाधानों को कुशलतापूर्वक गिना जा सकता है। इस प्रकार, यह समस्या ♯P में , लेकिन #P-पूर्ण नहीं हो सकती है जब तक #P=FP (जटिलता) है। यह आश्चर्यजनक होगा, क्योंकि इसका अर्थ यह होगा कि P = NP = PH । | ||
== कठोर काउंटिंग वर्जन के साथ आसान समस्याएं == | == कठोर काउंटिंग वर्जन के साथ आसान समस्याएं == | ||
कुछ #P-पूर्ण समस्याएं आसान ( | कुछ #P-पूर्ण समस्याएं आसान (बहुपद समय) समस्याओं के अनुरूप हैं। डीएनएफ में एक बूलियन सूत्र की संतुष्टि का निर्धारण करना आसान है: ऐसा सूत्र संतोषजनक है यदि और केवल यदि इसमें एक संतोषजनक संयोजन होता है (जिसमें एक चर और इसकी अस्वीकृति नहीं होती है), जबकि संतोषजनक नियतन की संख्या की गणना करना #P-पूर्ण है । इसके अतिरिक्त, संतोषजनक कार्यों की संख्या की गणना करने की तुलना में 2-संतोषजनकता तय करना आसान है। टोपोलॉजिकल सॉर्टिंग की संख्या गिनने के विपरीत टोपोलॉजिकल सॉर्टिंग आसान है। एक एकल मिलान (ग्राफ़ सिद्धांत) बहुपद समय में पाया जा सकता है, लेकिन सभी पूर्ण मिलानों की गणना करना #P-पूर्ण है। 1979 में [[Index.php?title=लेस्ली वैलिएंट|लेस्ली वैलिएंट]] के एक पेपर में सटीक मिलान वाली गिनती की समस्या एक आसान पी समस्या के अनुरूप पहली गिनती की समस्या थी, जिसे #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 | ||
| Line 43: | Line 43: | ||
| issue = 2| doi-access = free | | issue = 2| doi-access = free | ||
}}</ref> | }}</ref> | ||
== सन्निकटन == | == सन्निकटन == | ||
[[ | [[Index.php?title= प्रसंभाव्यतावादी एल्गोरिदम|प्रसंभाव्यतावादी एल्गोरिदम]] हैं जो उच्च संभावना के साथ कुछ #P-पूर्ण समस्याओं के लिए अच्छा अनुमान लगाते हैं। यह संभाव्य एल्गोरिदम की शक्ति के प्रदर्शनों में से एक है। | ||
कई #P-पूर्ण समस्याओं में एक [[बहुपद-समय सन्निकटन योजना]] | कई #P-पूर्ण समस्याओं में एक पूर्ण [[बहुपद-समय सन्निकटन योजना|बहुपद-समय]] यादृच्छिक [[बहुपद-समय सन्निकटन योजना|सन्निकटन योजना]] है, या FPRAS, जो, अनौपचारिक रूप से, उच्च संभाव्यता के साथ सटीकता की एक मनमाना कोटि के सन्निकटन का उत्पादन करेगी, जो समय में जो समस्या के आकार और आवश्यक सटीकता की डिग्री दोनों के संबंध में बहुपद है। [[मार्क जेरम]], लेस्ली वैलिएंट, और [[विजय वजीरानी]] ने दिखाया कि हर #P-पूर्ण समस्या में या तो एक FPRAS होता है, या अनुमानित रूप से असंभव है; यदि कोई बहुपद-समय एल्गोरिदम है जो लगातार एक #P-पूर्ण समस्या का अनुमान लगाता है जो सटीक उत्तर के इनपुट के आकार में बहुपद अनुपात के भीतर है, तो उस एल्गोरिदम का उपयोग FPRAS के निर्माण के लिए किया जा सकता है।<ref>{{cite journal | ||
| author = Mark R. Jerrum |author2=Leslie G. Valiant |author3=Vijay V. Vazirani | | author = Mark R. Jerrum |author2=Leslie G. Valiant |author3=Vijay V. Vazirani | ||
| title = Random Generation of Combinatorial Structures from a Uniform Distribution | | title = Random Generation of Combinatorial Structures from a Uniform Distribution | ||
| Line 59: | Line 57: | ||
| doi = 10.1016/0304-3975(86)90174-x | doi-access = free | | doi = 10.1016/0304-3975(86)90174-x | doi-access = free | ||
}}</ref> | }}</ref> | ||
== संदर्भ == | == संदर्भ == | ||
Revision as of 22:09, 19 May 2023
कम्प्यूटेशनल जटिलता सिद्धांत में #पी-पूर्ण समस्याएं (उच्चारण प्रखरपी पूर्ण या संख्या पी पूर्ण) एक जटिलता वर्ग बनाती हैं। इस जटिलता वर्ग की समस्याओं को निम्नलिखित दो गुण होने से परिभाषित किया गया है:
- समस्या ♯P में है, समस्याओं का वर्ग जिसे एक बहुपद-समय गैर-नियतात्मक ट्यूरिंग मशीन के स्वीकृत पथों की संख्या की गणना के रूप में परिभाषित किया जा सकता है।
- समस्या ♯P -कठोर है, जिसका अर्थ है कि #P में हर दूसरी समस्या में ट्यूरिंग कमी या बहुपद-समय की गिनती में कमी है। एक गिनती में कमी दूसरी समस्या के इनपुट से दी गई समस्या के इनपुट और दी गई समस्या के आउटपुट से दूसरी समस्या के आउटपुट तक बहुपद-समय के परिवर्तनों की एक जोड़ी है, जो दी गई समस्या के लिए किसी भी प्रक्रिया का उपयोग करके अन्य समस्या को हल करने की अनुमति देती है। एक ट्यूरिंग अपचयन दूसरी समस्या के लिए एक एल्गोरिथ्म है जो दी गई समस्या के लिए एक प्रक्रिया को बहुपद संख्या में आदेश करता है और उन आदेश के बाहर, बहुपदी समय फलन उपयोग करता है। कुछ कारको में पारसीमोनियस अपचयन, एक अधिक विशिष्ट प्रकार की कमी जो समाधानों की सटीक संख्या को संरक्षित करती है, का उपयोग किया जाता है।
#P-पूर्ण समस्याएँ कम से कम उतनी ही कठिन हैं जितनी कि NP-पूर्ण समस्याएँ।[1] #P-पूर्ण समस्या को हल करने के लिए एक बहुपद-समय एल्गोरिथ्म, यदि यह अस्तित्व में है, तो P विरुद्ध NP समस्या को P और NP के बराबर होने का अर्थ देकर हल करेगा। ऐसा कोई एल्गोरिथम ज्ञात नहीं है, न ही ऐसा कोई प्रमाण ज्ञात है कि ऐसा एल्गोरिथम उपस्थित नहीं है।
उदाहरण
- P-पूर्ण समस्याओं के उदाहरणों में सम्मिलित हैं:
- कितने भिन्न चर नियतन दिए गए सामान्य बूलियन सूत्र को संतुष्ट करेंगे? (#SAT)
- कितने अलग-अलग चर नियतन दिए गए असंबद्ध सामान्य रूप फॉर्मूले को संतुष्ट करेंगे?
- दी गई 2-संतोषजनक समस्या को कितने अलग-अलग चर नियतन संतुष्ट करेंगे?
- दिए गए द्विदलीय ग्राफ के लिए कितने पूर्ण मिलान हैं?
- किसी दिए गए मैट्रिक्स के स्थायी (गणित) का मान क्या है जिसकी प्रविष्टियाँ 0 या 1 हैं? (देखें #पी-01-स्थायी की पूर्णता।)
- किसी विशेष ग्राफ़ G के लिए k रंगों का उपयोग करने वाले कितने ग्राफ रंग हैं?
- दिए गए आंशिक रूप से क्रमित किए गए सेट के लिए कितने अलग रैखिक विस्तारण हैं, या समतुल्य, दिए गए एसाइक्लिक ग्राफ के लिए कितने अलग-अलग टोपोलॉजिकल क्रम हैं?[2]
ये सभी आवश्यक रूप से कक्षा ♯P के भी सदस्य हैं। एक गैर-उदाहरण के रूप में, 1-संतोषजनक समस्या के समाधान की गिनती के मामले पर विचार करें: चर राशि की एक श्रृंखला जो प्रत्येक व्यक्तिगत रूप से विवश हैं, लेकिन एक दूसरे के साथ कोई संबंध नहीं है। विलगन में प्रत्येक चर के लिए विकल्पों की संख्या को गुणा करके समाधानों को कुशलतापूर्वक गिना जा सकता है। इस प्रकार, यह समस्या ♯P में , लेकिन #P-पूर्ण नहीं हो सकती है जब तक #P=FP (जटिलता) है। यह आश्चर्यजनक होगा, क्योंकि इसका अर्थ यह होगा कि P = NP = PH ।
कठोर काउंटिंग वर्जन के साथ आसान समस्याएं
कुछ #P-पूर्ण समस्याएं आसान (बहुपद समय) समस्याओं के अनुरूप हैं। डीएनएफ में एक बूलियन सूत्र की संतुष्टि का निर्धारण करना आसान है: ऐसा सूत्र संतोषजनक है यदि और केवल यदि इसमें एक संतोषजनक संयोजन होता है (जिसमें एक चर और इसकी अस्वीकृति नहीं होती है), जबकि संतोषजनक नियतन की संख्या की गणना करना #P-पूर्ण है । इसके अतिरिक्त, संतोषजनक कार्यों की संख्या की गणना करने की तुलना में 2-संतोषजनकता तय करना आसान है। टोपोलॉजिकल सॉर्टिंग की संख्या गिनने के विपरीत टोपोलॉजिकल सॉर्टिंग आसान है। एक एकल मिलान (ग्राफ़ सिद्धांत) बहुपद समय में पाया जा सकता है, लेकिन सभी पूर्ण मिलानों की गणना करना #P-पूर्ण है। 1979 में लेस्ली वैलिएंट के एक पेपर में सटीक मिलान वाली गिनती की समस्या एक आसान पी समस्या के अनुरूप पहली गिनती की समस्या थी, जिसे #P-पूर्ण दिखाया गया था, जिसमें पहली बार कक्षा #P और #P-पूर्ण समस्याओं को भी परिभाषित किया गया था।[3]
सन्निकटन
प्रसंभाव्यतावादी एल्गोरिदम हैं जो उच्च संभावना के साथ कुछ #P-पूर्ण समस्याओं के लिए अच्छा अनुमान लगाते हैं। यह संभाव्य एल्गोरिदम की शक्ति के प्रदर्शनों में से एक है।
कई #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.
