♯पी-पूर्ण
कम्प्यूटेशनल जटिलता सिद्धांत में #पी-पूर्ण समस्याएं (उच्चारण तेज पी पूर्ण या संख्या पी पूर्ण) एक जटिलता वर्ग बनाती हैं। इस जटिलता वर्ग की समस्याओं को निम्नलिखित दो गुण होने से परिभाषित किया गया है:
- समस्या ♯P|#P में है, समस्याओं का वर्ग जिसे एक बहुपद-समय गैर-नियतात्मक ट्यूरिंग मशीन के स्वीकृत पथों की संख्या की गणना के रूप में परिभाषित किया जा सकता है।
- समस्या ♯P|#P-हार्ड है, जिसका अर्थ है कि #P में हर दूसरी समस्या में ट्यूरिंग कमी या बहुपद-समय की गिनती में कमी है। एक गिनती में कमी दूसरी समस्या के इनपुट से दी गई समस्या के इनपुट और दी गई समस्या के आउटपुट से दूसरी समस्या के आउटपुट तक बहुपद-समय के परिवर्तनों की एक जोड़ी है, जो दी गई समस्या के लिए किसी भी सबरूटीन का उपयोग करके अन्य समस्या को हल करने की अनुमति देती है। संकट। एक ट्यूरिंग रिडक्शन दूसरी समस्या के लिए एक एल्गोरिथ्म है जो दी गई समस्या के लिए एक सबरूटीन को बहुपद संख्या में कॉल करता है और उन कॉलों के बाहर, बहुपदी समय फलन उपयोग करता है। कुछ मामलों में पारिश्रमिक कटौती, एक अधिक विशिष्ट प्रकार की कमी जो समाधानों की सटीक संख्या को संरक्षित करती है, का उपयोग किया जाता है।
#P-complete समस्याएँ कम से कम उतनी ही कठिन हैं जितनी कि NP-पूर्ण समस्याएँ।[1] #P-पूर्ण समस्या को हल करने के लिए एक बहुपद-समय एल्गोरिथ्म, यदि यह अस्तित्व में है, तो P बनाम NP समस्या को P और NP के बराबर होने का अर्थ देकर हल करेगा। ऐसा कोई एल्गोरिथम ज्ञात नहीं है, न ही ऐसा कोई प्रमाण ज्ञात है कि ऐसा एल्गोरिथम मौजूद नहीं है।
उदाहरण
- P-पूर्ण समस्याओं के उदाहरणों में शामिल हैं:
- कितने भिन्न चर नियतन दिए गए सामान्य बूलियन सूत्र को संतुष्ट करेंगे? (शार्प-सैट|#सैट)
- कितने अलग-अलग वैरिएबल असाइनमेंट दिए गए असंबद्ध सामान्य रूप फॉर्मूले को संतुष्ट करेंगे?
- दी गई 2-संतोषजनक समस्या को कितने अलग-अलग चर असाइनमेंट संतुष्ट करेंगे?
- दिए गए द्विदलीय ग्राफ के लिए कितने पूर्ण मिलान हैं?
- किसी दिए गए मैट्रिक्स के स्थायी (गणित) का मान क्या है जिसकी प्रविष्टियाँ 0 या 1 हैं? (देखें ♯पी-01-स्थायी की पूर्णता|#पी-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.
