फंक्शन (फलन) समस्या: Difference between revisions
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{short description|Type of computational problem}} | {{short description|Type of computational problem}} | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, | [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, फलन समस्या [[कम्प्यूटेशनल समस्या]] है जहां प्रत्येक इनपुट के लिए आउटपुट (कुल फलन का) अपेक्षित है किन्तु आउटपुट [[निर्णय समस्या]] की तुलना में अधिक जटिल है। कार्य समस्याओं के लिए आउटपुट केवल 'हां' या 'नहीं' नहीं है। | ||
== औपचारिक परिभाषा == | == औपचारिक परिभाषा == | ||
कार्यात्मक समस्या <math>P</math> [[ | एक कार्यात्मक समस्या <math>P</math> को एक ने इच्छानुसार से [[वर्णमाला (कंप्यूटर विज्ञान)]] <math>\Sigma</math> के संबंध <math>R</math> द्वारा परिभाषित किया गया है। | ||
: <math>R \subseteq \Sigma^* \times \Sigma^*.</math> | : <math>R \subseteq \Sigma^* \times \Sigma^*.</math> | ||
एक एल्गोरिथ्म <math>P</math> को हल करता है यदि प्रत्येक इनपुट <math>x</math> के लिए जैसे कि R में एक <math>y</math> संतोषजनक <math>(x, y) \in R</math> उपस्थित है, तो एल्गोरिथ्म एक ऐसा <math>y</math> उत्पन्न करता है, और यदि ऐसा कोई <math>y</math> नहीं है तो यह अस्वीकार कर देता है। | |||
एक प्रॉमिस फलन समस्या को कुछ भी करने की अनुमति है (इस प्रकार समाप्त नहीं हो सकता है) यदि ऐसा कोई <math>y</math> उपस्थित नहीं है। | |||
== उदाहरण == | == उदाहरण == | ||
कार्यात्मक बूलियन संतुष्टि समस्या | कार्यात्मक बूलियन संतुष्टि समस्या एफएसएटी द्वारा संक्षेप में प्रसिद्ध कार्य समस्या दी गई है। समस्या जो बूलियन संतुष्टि समस्या निर्णय समस्या से निकटता से संबंधित है निम्नानुसार तैयार किया जा सकता है: | ||
: | :चर <math>x_1, \ldots, x_n</math>के साथ एक बूलियन सूत्र <math>\varphi</math> दिया गया है एक असाइनमेंट <math>x_i \rightarrow \{ \text{TRUE}, \text{FALSE} \}</math> खोजे जिससे <math>\varphi</math> का मूल्यांकन करे <math>\text{TRUE}</math> या तय करें कि ऐसा कोई असाइनमेंट उपस्थित नहीं है | ||
इस स्थितियों में संबंध <math>R</math> उपयुक्त एन्कोडेड बूलियन | इस स्थितियों में संबंध <math>R</math> उपयुक्त एन्कोडेड बूलियन सूत्रों और संतोषजनक असाइनमेंट के टुपल्स द्वारा दिया गया है। | ||
जबकि | इस स्थिति में संबंध <math>R</math> उपयुक्त रूप से एन्कोडेड बूलियन फ़ार्मुलों और संतोषजनक असाइनमेंट के टुपल्स द्वारा दिया गया है। जबकि एफएसएटी एल्गोरिद्म, सूत्र <math>\varphi</math> के साथ विपरीत जाता है को केवल "असंतोषजनक" या "संतोषजनक" वापस करने की आवश्यकता होती है, बाद वाले स्थिति में एफएसएटी एल्गोरिद्म को कुछ संतोषजनक असाइनमेंट वापस करने की आवश्यकता होती है। | ||
अन्य उल्लेखनीय उदाहरणों में [[ट्रैवलिंग सेल्समैन की समस्या]] सम्मिलित है | अन्य उल्लेखनीय उदाहरणों में [[ट्रैवलिंग सेल्समैन की समस्या]] सम्मिलित है जो सेल्समैन द्वारा लिए गए मार्ग के बारे में पूछती है और पूर्णांक गुणनखंडन समस्या जो कारकों की सूची के लिए पूछती है। | ||
== अन्य जटिलता वर्गों से | == अन्य जटिलता वर्गों से संबं == | ||
इच्छानुसार निर्णय समस्या | कक्षा '''NP''' में इच्छानुसार निर्णय समस्या <math>L</math> पर विचार करें '''NP''' की परिभाषा के अनुसार प्रत्येक समस्या का उदाहरण <math>x</math> जिसका उत्तर 'हां' में दिया गया है, में एक बहुपद-आकार का प्रमाण पत्र <math>y</math> है जो 'हां' उत्तर के प्रमाण के रूप में कार्य करता है। इस प्रकार इन टुपल्स <math>(x,y)</math> का सेट एक संबंध बनाता है, "<math>L</math> में दिए गए <math>x</math>, <math>x</math> के लिए प्रमाण पत्र <math>y</math> खोजें" फलन समस्या का प्रतिनिधित्व करता है। इस फलन समस्या को <math>L</math> का फलन प्रकार कहा जाता है; यह '''FNP''' वर्ग के अंतर्गत आता है। | ||
'''FNP''' को '''NP''' के कार्यात्मक वर्ग एनालॉग के रूप में माना जा सकता है जिसमें '''FNP''' समस्याओं के समाधान कुशलता से हो सकते हैं (अर्थात इनपुट की लंबाई के संदर्भ में बहुपद समय में) 'सत्यापित किन्तु आवश्यक नहीं कि कुशलतापूर्वक पाया गया इसके विपरीत वर्ग [[एफपी (जटिलता)]] जिसे पी के फलन क्लास एनालॉग के रूप में माना जा सकता है में फलन समस्याएं होती हैं जिनके समाधान बहुपद समय में पाए जा सकते हैं। | |||
== स्व-न्यूनीकरण == | == स्व-न्यूनीकरण == | ||
ध्यान दें कि ऊपर प्रस्तुत की गई | ध्यान दें कि ऊपर प्रस्तुत की गई समस्या '''FSAT''' को सबरूटीन के लिए केवल बहुपद रूप से कई कॉलों का उपयोग करके हल किया जा सकता है जो '''SAT''' समस्या का निर्णय करता है: एक एल्गोरिथम पहले पूछ सकता है कि क्या सूत्र <math>\varphi</math> संतोषजनक है। उसके बाद एल्गोरिथ्म चर <math>x_1</math> को सत्य में ठीक कर सकता है और फिर से पूछ सकता है। यदि परिणामी सूत्र अभी भी संतोषजनक है तो एल्गोरिथम <math>x_1</math> को TRUE पर स्थिर रखता है और <math>x_2</math> को ठीक करना जारी रखता है, अन्यथा यह तय करता है कि <math>x_1</math> को गलत होना चाहिए और जारी रहता है। इस प्रकार, एसएटी का निर्णय लेने वाले ओरेकल का उपयोग करके बहुपद समय में '''FSAT''' हल करने योग्य है। सामान्यतः एनपी में एक समस्या को स्व-कम करने योग्य कहा जाता है यदि मूल समस्या का निर्णय लेने वाले ओरेकल का उपयोग करके बहुपद समय में इसका कार्य संस्करण हल किया जा सकता है। हर एनपी-पूर्ण समस्या स्व-कम करने योग्य है। यह अनुमान लगाया गया है कि पूर्णांक गुणनखंडन समस्या स्व-कम करने योग्य नहीं है, क्योंकि यह तय करना कि पूर्णांक अभाज्य है या नहीं, P (आसान) में है, जबकि पूर्णांक गुणनखंड समस्या को शास्त्रीय कंप्यूटर के लिए कठिन माना जाता है<ref name="AKS">{{cite journal |first1=Manindra |last1=Agrawal |first2=Neeraj |last2=Kayal |first3=Nitin |last3=Saxena |url=http://www.cse.iitk.ac.in/users/manindra/algebra/primality_v6.pdf |title=PRIMES, P में है|journal=[[Annals of Mathematics]] |volume=160 |year=2004 |issue=2 |pages=781–793 |doi=10.4007/annals.2004.160.781 |jstor=3597229 |doi-access=free }}</ref> आत्म-कम करने की कई (थोड़ी अलग) धारणाएँ हैं।<ref>{{cite journal |first= K.|last= Ko|title= स्व-न्यूनीकरण और कमजोर पी-चयनात्मकता पर|journal= Journal of Computer and System Sciences|volume= 26|issue=2|pages=209–221|year=1983}}</ref><ref>{{cite journal |first= C.|last=Schnorr|title=स्व-कम करने योग्य समस्याओं के लिए इष्टतम एल्गोरिदम|journal=In S. Michaelson and R. Milner, editors, Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming|pages=322–337|year=1976}}</ref><ref>{{cite journal |first=A.|last=Selman|title=प्राकृतिक स्व-कम करने योग्य सेट|journal=SIAM Journal on Computing|volume= 17|issue=5|pages=989–996|year=1988}}</ref> | ||
आत्म-कम करने की कई (थोड़ी अलग) धारणाएँ हैं।<ref>{{cite journal |first= K.|last= Ko|title= स्व-न्यूनीकरण और कमजोर पी-चयनात्मकता पर|journal= Journal of Computer and System Sciences|volume= 26|issue=2|pages=209–221|year=1983}}</ref><ref>{{cite journal |first= C.|last=Schnorr|title=स्व-कम करने योग्य समस्याओं के लिए इष्टतम एल्गोरिदम|journal=In S. Michaelson and R. Milner, editors, Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming|pages=322–337|year=1976}}</ref><ref>{{cite journal |first=A.|last=Selman|title=प्राकृतिक स्व-कम करने योग्य सेट|journal=SIAM Journal on Computing|volume= 17|issue=5|pages=989–996|year=1988}}</ref> | |||
== कटौती और पूर्ण समस्याएं == | == कटौती और पूर्ण समस्याएं == | ||
फलन समस्याओं को निर्णय समस्याओं की तरह बहुत कम किया जा सकता है: फलन समस्याओं <math>\Pi_R</math> और <math>\Pi_S</math> को देखते हुए हम कहते हैं कि <math>\Pi_R</math><math>\Pi_S</math> तक कम हो जाता है यदि बहुपद-समय गणना योग्य फलन <math>f</math> और <math>g</math> उपस्थित हैं जैसे कि सभी उदाहरणों के लिए <math>x</math> का <math>R</math> और संभावित समाधान <math>y</math> <math>S</math> का यह धारण करता है | |||
*यदि <math>x</math> | *यदि <math>x</math> का <math>R</math>-समाधान है, तो <math>f(x)</math> का <math>S</math>-समाधान है। | ||
*<math>(f(x), y) \in S \implies (x, g(x,y)) \in R.</math> | *<math>(f(x), y) \in S \implies (x, g(x,y)) \in R.</math> | ||
इसलिए एनपी-पूर्ण समस्या के अनुरूप एफएनपी-पूर्ण समस्याओं को परिभाषित करना संभव है: | इसलिए एनपी-पूर्ण समस्या के अनुरूप एफएनपी-पूर्ण समस्याओं को परिभाषित करना संभव है: | ||
समस्या <math>\Pi_R</math> एफएनपी -पूर्ण है यदि एफएनपी में प्रत्येक समस्या को | एक समस्या <math>\Pi_R</math> एफएनपी -पूर्ण है यदि एफएनपी में प्रत्येक समस्या को <math>\Pi_R</math> तक कम किया जा सकता है। एफएनपी-पूर्ण समस्याओं की जटिलता वर्ग एफएनपी-सी या एफएनपीसी द्वारा दर्शाया गया है। इसलिए समस्या एफएसएटी भी एक एफएनपी -पूर्ण समस्या है, और यह रखती है कि <math>\mathbf{P} = \mathbf{NP}</math> यदि और केवल यदि <math>\mathbf{FP} = \mathbf{FNP}</math>। | ||
== कुल कार्य समस्याएं == | == कुल कार्य समस्याएं == | ||
फलन समस्याओं को परिभाषित करने के लिए उपयोग किए जाने वाले संबंध <math>R(x, y)</math> में अपूर्ण होने की कमी है: प्रत्येक इनपुट <math>x</math> का प्रतिरूप <math>y</math> ऐसा नहीं है कि <math>(x, y) \in R</math> इसलिए प्रमाणों की संगणना का प्रश्न इससे अलग नहीं है उनके अस्तित्व का सवाल इस समस्या को दूर करने के लिए यह सुविधाजनक है कि वर्ग [[TFNP|टीएफएनपी]] को एफएनपी के उपवर्ग के रूप में उत्पन्न करने वाले कुल संबंधों के लिए कार्य समस्याओं के प्रतिबंध पर विचार किया जाए। इस वर्ग में कुछ सामरिक खेलों में शुद्ध नैश संतुलन की गणना जैसी समस्याएं सम्मिलित हैं जहां एक समाधान उपस्थित होने की आश्वासन है। इसके अतिरिक्त, यदि [[TFNP|टीएफएनपी]] में कोई एफएनपी-सम्पूर्ण समस्या है तो यह <math>\mathbf{NP} = \textbf{co-NP}</math> के बाद आती है। | |||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 07:52, 25 May 2023
कम्प्यूटेशनल जटिलता सिद्धांत में, फलन समस्या कम्प्यूटेशनल समस्या है जहां प्रत्येक इनपुट के लिए आउटपुट (कुल फलन का) अपेक्षित है किन्तु आउटपुट निर्णय समस्या की तुलना में अधिक जटिल है। कार्य समस्याओं के लिए आउटपुट केवल 'हां' या 'नहीं' नहीं है।
औपचारिक परिभाषा
एक कार्यात्मक समस्या को एक ने इच्छानुसार से वर्णमाला (कंप्यूटर विज्ञान) के संबंध द्वारा परिभाषित किया गया है।
एक एल्गोरिथ्म को हल करता है यदि प्रत्येक इनपुट के लिए जैसे कि R में एक संतोषजनक उपस्थित है, तो एल्गोरिथ्म एक ऐसा उत्पन्न करता है, और यदि ऐसा कोई नहीं है तो यह अस्वीकार कर देता है।
एक प्रॉमिस फलन समस्या को कुछ भी करने की अनुमति है (इस प्रकार समाप्त नहीं हो सकता है) यदि ऐसा कोई उपस्थित नहीं है।
उदाहरण
कार्यात्मक बूलियन संतुष्टि समस्या एफएसएटी द्वारा संक्षेप में प्रसिद्ध कार्य समस्या दी गई है। समस्या जो बूलियन संतुष्टि समस्या निर्णय समस्या से निकटता से संबंधित है निम्नानुसार तैयार किया जा सकता है:
- चर के साथ एक बूलियन सूत्र दिया गया है एक असाइनमेंट खोजे जिससे का मूल्यांकन करे या तय करें कि ऐसा कोई असाइनमेंट उपस्थित नहीं है
इस स्थितियों में संबंध उपयुक्त एन्कोडेड बूलियन सूत्रों और संतोषजनक असाइनमेंट के टुपल्स द्वारा दिया गया है।
इस स्थिति में संबंध उपयुक्त रूप से एन्कोडेड बूलियन फ़ार्मुलों और संतोषजनक असाइनमेंट के टुपल्स द्वारा दिया गया है। जबकि एफएसएटी एल्गोरिद्म, सूत्र के साथ विपरीत जाता है को केवल "असंतोषजनक" या "संतोषजनक" वापस करने की आवश्यकता होती है, बाद वाले स्थिति में एफएसएटी एल्गोरिद्म को कुछ संतोषजनक असाइनमेंट वापस करने की आवश्यकता होती है।
अन्य उल्लेखनीय उदाहरणों में ट्रैवलिंग सेल्समैन की समस्या सम्मिलित है जो सेल्समैन द्वारा लिए गए मार्ग के बारे में पूछती है और पूर्णांक गुणनखंडन समस्या जो कारकों की सूची के लिए पूछती है।
अन्य जटिलता वर्गों से संबं
कक्षा NP में इच्छानुसार निर्णय समस्या पर विचार करें NP की परिभाषा के अनुसार प्रत्येक समस्या का उदाहरण जिसका उत्तर 'हां' में दिया गया है, में एक बहुपद-आकार का प्रमाण पत्र है जो 'हां' उत्तर के प्रमाण के रूप में कार्य करता है। इस प्रकार इन टुपल्स का सेट एक संबंध बनाता है, " में दिए गए , के लिए प्रमाण पत्र खोजें" फलन समस्या का प्रतिनिधित्व करता है। इस फलन समस्या को का फलन प्रकार कहा जाता है; यह FNP वर्ग के अंतर्गत आता है।
FNP को NP के कार्यात्मक वर्ग एनालॉग के रूप में माना जा सकता है जिसमें FNP समस्याओं के समाधान कुशलता से हो सकते हैं (अर्थात इनपुट की लंबाई के संदर्भ में बहुपद समय में) 'सत्यापित किन्तु आवश्यक नहीं कि कुशलतापूर्वक पाया गया इसके विपरीत वर्ग एफपी (जटिलता) जिसे पी के फलन क्लास एनालॉग के रूप में माना जा सकता है में फलन समस्याएं होती हैं जिनके समाधान बहुपद समय में पाए जा सकते हैं।
स्व-न्यूनीकरण
ध्यान दें कि ऊपर प्रस्तुत की गई समस्या FSAT को सबरूटीन के लिए केवल बहुपद रूप से कई कॉलों का उपयोग करके हल किया जा सकता है जो SAT समस्या का निर्णय करता है: एक एल्गोरिथम पहले पूछ सकता है कि क्या सूत्र संतोषजनक है। उसके बाद एल्गोरिथ्म चर को सत्य में ठीक कर सकता है और फिर से पूछ सकता है। यदि परिणामी सूत्र अभी भी संतोषजनक है तो एल्गोरिथम को TRUE पर स्थिर रखता है और को ठीक करना जारी रखता है, अन्यथा यह तय करता है कि को गलत होना चाहिए और जारी रहता है। इस प्रकार, एसएटी का निर्णय लेने वाले ओरेकल का उपयोग करके बहुपद समय में FSAT हल करने योग्य है। सामान्यतः एनपी में एक समस्या को स्व-कम करने योग्य कहा जाता है यदि मूल समस्या का निर्णय लेने वाले ओरेकल का उपयोग करके बहुपद समय में इसका कार्य संस्करण हल किया जा सकता है। हर एनपी-पूर्ण समस्या स्व-कम करने योग्य है। यह अनुमान लगाया गया है कि पूर्णांक गुणनखंडन समस्या स्व-कम करने योग्य नहीं है, क्योंकि यह तय करना कि पूर्णांक अभाज्य है या नहीं, P (आसान) में है, जबकि पूर्णांक गुणनखंड समस्या को शास्त्रीय कंप्यूटर के लिए कठिन माना जाता है[1] आत्म-कम करने की कई (थोड़ी अलग) धारणाएँ हैं।[2][3][4]
कटौती और पूर्ण समस्याएं
फलन समस्याओं को निर्णय समस्याओं की तरह बहुत कम किया जा सकता है: फलन समस्याओं और को देखते हुए हम कहते हैं कि तक कम हो जाता है यदि बहुपद-समय गणना योग्य फलन और उपस्थित हैं जैसे कि सभी उदाहरणों के लिए का और संभावित समाधान का यह धारण करता है
- यदि का -समाधान है, तो का -समाधान है।
इसलिए एनपी-पूर्ण समस्या के अनुरूप एफएनपी-पूर्ण समस्याओं को परिभाषित करना संभव है:
एक समस्या एफएनपी -पूर्ण है यदि एफएनपी में प्रत्येक समस्या को तक कम किया जा सकता है। एफएनपी-पूर्ण समस्याओं की जटिलता वर्ग एफएनपी-सी या एफएनपीसी द्वारा दर्शाया गया है। इसलिए समस्या एफएसएटी भी एक एफएनपी -पूर्ण समस्या है, और यह रखती है कि यदि और केवल यदि ।
कुल कार्य समस्याएं
फलन समस्याओं को परिभाषित करने के लिए उपयोग किए जाने वाले संबंध में अपूर्ण होने की कमी है: प्रत्येक इनपुट का प्रतिरूप ऐसा नहीं है कि इसलिए प्रमाणों की संगणना का प्रश्न इससे अलग नहीं है उनके अस्तित्व का सवाल इस समस्या को दूर करने के लिए यह सुविधाजनक है कि वर्ग टीएफएनपी को एफएनपी के उपवर्ग के रूप में उत्पन्न करने वाले कुल संबंधों के लिए कार्य समस्याओं के प्रतिबंध पर विचार किया जाए। इस वर्ग में कुछ सामरिक खेलों में शुद्ध नैश संतुलन की गणना जैसी समस्याएं सम्मिलित हैं जहां एक समाधान उपस्थित होने की आश्वासन है। इसके अतिरिक्त, यदि टीएफएनपी में कोई एफएनपी-सम्पूर्ण समस्या है तो यह के बाद आती है।
यह भी देखें
- निर्णय समस्या
- खोज समस्या
- गिनती की समस्या (जटिलता)
- अनुकूलन समस्या
संदर्भ
- Raymond Greenlaw, H. James Hoover, Fundamentals of the theory of computation: principles and practice, Morgan Kaufmann, 1998, ISBN 1-55860-474-X, p. 45-51
- Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2008, ISBN 0-13-228806-0, section 28.10 "The problem classes FP and FNP", pp. 689–694
- ↑ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES, P में है" (PDF). Annals of Mathematics. 160 (2): 781–793. doi:10.4007/annals.2004.160.781. JSTOR 3597229.
- ↑ Ko, K. (1983). "स्व-न्यूनीकरण और कमजोर पी-चयनात्मकता पर". Journal of Computer and System Sciences. 26 (2): 209–221.
- ↑ Schnorr, C. (1976). "स्व-कम करने योग्य समस्याओं के लिए इष्टतम एल्गोरिदम". In S. Michaelson and R. Milner, editors, Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming: 322–337.
- ↑ Selman, A. (1988). "प्राकृतिक स्व-कम करने योग्य सेट". SIAM Journal on Computing. 17 (5): 989–996.
