फंक्शन (फलन) समस्या: 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>R</math> मनमानी [[वर्णमाला (कंप्यूटर विज्ञान)]] के ओवर [[स्ट्रिंग (कंप्यूटर विज्ञान)]] <math>\Sigma</math>: | ||
: <math>R \subseteq \Sigma^* \times \Sigma^*.</math> | : <math>R \subseteq \Sigma^* \times \Sigma^*.</math> | ||
एल्गोरिदम हल करता है <math>P</math> यदि | एल्गोरिदम हल करता है <math>P</math> यदि हर इनपुट के लिए <math>x</math> ऐसा है कि वहाँ उपस्थित है <math>y</math> संतुष्टि देने वाला <math>(x, y) \in R</math>, एल्गोरिथ्म ऐसा उत्पन्न करता है <math>y</math>, और यदि ऐसा नहीं है <math>y</math>, यह अस्वीकार करता है। | ||
वादा | वादा फलन समस्या को कुछ भी करने की अनुमति है (इस प्रकार समाप्त नहीं हो सकता है) यदि ऐसा नहीं है <math>y</math> मौजूद। | ||
== उदाहरण == | == उदाहरण == | ||
कार्यात्मक बूलियन संतुष्टि समस्या, एफएसएटी द्वारा संक्षेप में | कार्यात्मक बूलियन संतुष्टि समस्या, एफएसएटी द्वारा संक्षेप में प्रसिद्ध कार्य समस्या दी गई है। समस्या, जो बूलियन संतुष्टि समस्या निर्णय समस्या से निकटता से संबंधित है, को निम्नानुसार तैयार किया जा सकता है: | ||
: बूलियन सूत्र दिया गया <math>\varphi</math> चर के साथ <math>x_1, \ldots, x_n</math>, | : बूलियन सूत्र दिया गया <math>\varphi</math> चर के साथ <math>x_1, \ldots, x_n</math>, असाइनमेंट खोजें <math>x_i \rightarrow \{ \text{TRUE}, \text{FALSE} \}</math> ऐसा है कि <math>\varphi</math> का मूल्यांकन करता है <math>\text{TRUE}</math> या तय करें कि ऐसा कोई असाइनमेंट उपस्थित नहीं है। | ||
इस स्थितियों में संबंध <math>R</math> उपयुक्त एन्कोडेड बूलियन फ़ार्मुलों और संतोषजनक असाइनमेंट के टुपल्स द्वारा दिया गया है। | इस स्थितियों में संबंध <math>R</math> उपयुक्त एन्कोडेड बूलियन फ़ार्मुलों और संतोषजनक असाइनमेंट के टुपल्स द्वारा दिया गया है। | ||
जबकि | जबकि SAT एल्गोरिथम, सूत्र के साथ खिलाया जाता है <math>\varphi</math>, केवल असंतोषजनक या संतोषजनक लौटने की आवश्यकता है, एफएसएटी एल्गोरिदम को बाद के स्थितियों में कुछ संतोषजनक असाइनमेंट वापस करने की आवश्यकता है। | ||
अन्य उल्लेखनीय उदाहरणों में [[ट्रैवलिंग सेल्समैन की समस्या]] सम्मिलित | अन्य उल्लेखनीय उदाहरणों में [[ट्रैवलिंग सेल्समैन की समस्या]] सम्मिलित है, जो सेल्समैन द्वारा लिए गए मार्ग के बारे में पूछती है, और पूर्णांक गुणनखंडन समस्या, जो कारकों की सूची के लिए पूछती है। | ||
== अन्य जटिलता वर्गों से संबंध == | == अन्य जटिलता वर्गों से संबंध == | ||
इच्छानुसार | इच्छानुसार निर्णय समस्या पर विचार करें <math>L</math> कक्षा एनपी (जटिलता) में। एनपी की परिभाषा के अनुसार, प्रत्येक समस्या का उदाहरण <math>x</math> जिसका उत्तर 'हां' में बहुपद आकार का प्रमाण पत्र है <math>y</math> जो 'हां' उत्तर के प्रमाण के रूप में कार्य करता है। इस प्रकार, इन टुपल्स का समुच्चय <math>(x,y)</math> दी गई फलन समस्या को निरूपित करते हुए संबंध बनाता है <math>x</math> में <math>L</math>, प्रमाणपत्र प्राप्त करें <math>y</math> के लिए <math>x</math>. इस फ़ंक्शन समस्या को फ़ंक्शन वेरिएंट कहा जाता है <math>L</math>; यह वर्ग एफएनपी (जटिलता) से संबंधित है। | ||
एफएनपी को एनपी के कार्यात्मक वर्ग एनालॉग के रूप में माना जा सकता है, जिसमें एफएनपी समस्याओं के समाधान कुशलता से हो सकते हैं (अर्थात , इनपुट की लंबाई के संदर्भ में बहुपद समय में) 'सत्यापित'', किन्तु आवश्यक | एफएनपी को एनपी के कार्यात्मक वर्ग एनालॉग के रूप में माना जा सकता है, जिसमें एफएनपी समस्याओं के समाधान कुशलता से हो सकते हैं (अर्थात , इनपुट की लंबाई के संदर्भ में बहुपद समय में) 'सत्यापित'', किन्तु आवश्यक नहीं कि कुशलतापूर्वक'' पाया गया ''। इसके विपरीत, वर्ग [[एफपी (जटिलता)]], जिसे पी के फ़ंक्शन क्लास एनालॉग के रूप में माना जा सकता है, में फ़ंक्शन समस्याएं होती हैं जिनके समाधान बहुपद समय में पाए जा सकते हैं। | ||
== स्व-न्यूनीकरण == | == स्व-न्यूनीकरण == | ||
ध्यान दें कि ऊपर प्रस्तुत की गई एफएसएटी समस्या को सबरूटीन के लिए केवल बहुपद रूप से कई कॉलों का उपयोग करके हल किया जा सकता है जो एसएटी समस्या का फैसला करता है: | ध्यान दें कि ऊपर प्रस्तुत की गई एफएसएटी समस्या को सबरूटीन के लिए केवल बहुपद रूप से कई कॉलों का उपयोग करके हल किया जा सकता है जो एसएटी समस्या का फैसला करता है: एल्गोरिदम पहले पूछ सकता है कि क्या सूत्र <math>\varphi</math> संतोषजनक है। उसके बाद एल्गोरिथ्म वेरिएबल को ठीक कर सकता है <math>x_1</math> सही करने के लिए और फिर से पूछें। यदि परिणामी सूत्र अभी भी संतोषजनक है तो एल्गोरिथम रहता है <math>x_1</math> सत्य पर नियत है और ठीक करना जारी रखता है <math>x_2</math>, अन्यथा यह तय करता है <math>x_1</math>असत्य होना चाहिए और जारी रहना चाहिए। इस प्रकार, एसएटी का निर्णय लेने वाली [[ओरेकल मशीन]] का उपयोग करके बहुपद समय में एफएसएटी हल करने योग्य है। सामान्यतः , एनपी में समस्या को ''सेल्फ-रिड्यूसिबल'' कहा जाता है, यदि इसके फलन वेरिएंट को बहुपद समय में मूल समस्या का निर्णय लेने वाले ओरेकल का उपयोग करके हल किया जा सकता है। हर एनपी-पूर्ण समस्या स्व-कम करने योग्य है। यह अनुमान है {{By whom|date=February 2020}} कि पूर्णांक गुणनखंडन समस्या स्व-कम करने योग्य नहीं है, क्योंकि यह तय करना कि पूर्णांक अभाज्य है या नहीं, पी (आसान) में है,<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> | ||
| Line 36: | Line 36: | ||
फ़ंक्शन समस्याएं [[कमी (जटिलता)]] हो सकती हैं जैसे निर्णय समस्याएं: दी गई फ़ंक्शन समस्याएं <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>\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>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>. एफएनपी-पूर्ण समस्याओं की जटिलता वर्ग एफएनपी-सी या एफएनपीसी द्वारा दर्शाया गया है। इसलिए समस्या FSAT भी एफएनपी -सम्पूर्ण समस्या है, और यह इसे मानती है <math>\mathbf{P} = \mathbf{NP}</math> यदि और केवल यदि <math>\mathbf{FP} = \mathbf{FNP}</math>. | ||
== कुल कार्य समस्याएं == | == कुल कार्य समस्याएं == | ||
रिश्ता <math>R(x, y)</math> फ़ंक्शन समस्याओं को परिभाषित करने के लिए उपयोग किए जाने वाले अपूर्ण होने का दोष है: प्रत्येक इनपुट नहीं <math>x</math> | रिश्ता <math>R(x, y)</math> फ़ंक्शन समस्याओं को परिभाषित करने के लिए उपयोग किए जाने वाले अपूर्ण होने का दोष है: प्रत्येक इनपुट नहीं <math>x</math> समकक्ष है <math>y</math> ऐसा है कि <math>(x, y) \in R</math>. इसलिए प्रमाणों की संगणना का प्रश्न उनके अस्तित्व के प्रश्न से अलग नहीं है। इस समस्या को दूर करने के लिए यह सुविधाजनक है कि वर्ग [[TFNP|T एफएनपी]] को एफएनपी के उपवर्ग के रूप में उत्पन्न करने वाले कुल संबंधों के लिए कार्य समस्याओं के प्रतिबंध पर विचार किया जाए। इस वर्ग में कुछ सामरिक खेलों में शुद्ध [[नैश संतुलन]] की गणना जैसी समस्याएं सम्मिलित हैं जहां समाधान उपस्थित होने की गारंटी है। इसके अतिरिक्त , यदि T एफएनपी में कोई एफएनपी -सम्पूर्ण समस्या है, तो यह उसका अनुसरण करती है <math>\mathbf{NP} = \textbf{co-NP}</math>. | ||
== यह भी देखें == | == यह भी देखें == | ||
Revision as of 22:09, 24 May 2023
कम्प्यूटेशनल जटिलता सिद्धांत में, फ़ंक्शन समस्या कम्प्यूटेशनल समस्या है जहां प्रत्येक इनपुट के लिए आउटपुट (कुल फ़ंक्शन का) अपेक्षित है, किन्तु आउटपुट निर्णय समस्या की तुलना में अधिक जटिल है। कार्य समस्याओं के लिए, आउटपुट केवल 'हां' या 'नहीं' नहीं है।
औपचारिक परिभाषा
कार्यात्मक समस्या संबंध (गणित) द्वारा परिभाषित किया गया है मनमानी वर्णमाला (कंप्यूटर विज्ञान) के ओवर स्ट्रिंग (कंप्यूटर विज्ञान) :
एल्गोरिदम हल करता है यदि हर इनपुट के लिए ऐसा है कि वहाँ उपस्थित है संतुष्टि देने वाला , एल्गोरिथ्म ऐसा उत्पन्न करता है , और यदि ऐसा नहीं है , यह अस्वीकार करता है।
वादा फलन समस्या को कुछ भी करने की अनुमति है (इस प्रकार समाप्त नहीं हो सकता है) यदि ऐसा नहीं है मौजूद।
उदाहरण
कार्यात्मक बूलियन संतुष्टि समस्या, एफएसएटी द्वारा संक्षेप में प्रसिद्ध कार्य समस्या दी गई है। समस्या, जो बूलियन संतुष्टि समस्या निर्णय समस्या से निकटता से संबंधित है, को निम्नानुसार तैयार किया जा सकता है:
- बूलियन सूत्र दिया गया चर के साथ , असाइनमेंट खोजें ऐसा है कि का मूल्यांकन करता है या तय करें कि ऐसा कोई असाइनमेंट उपस्थित नहीं है।
इस स्थितियों में संबंध उपयुक्त एन्कोडेड बूलियन फ़ार्मुलों और संतोषजनक असाइनमेंट के टुपल्स द्वारा दिया गया है।
जबकि SAT एल्गोरिथम, सूत्र के साथ खिलाया जाता है , केवल असंतोषजनक या संतोषजनक लौटने की आवश्यकता है, एफएसएटी एल्गोरिदम को बाद के स्थितियों में कुछ संतोषजनक असाइनमेंट वापस करने की आवश्यकता है।
अन्य उल्लेखनीय उदाहरणों में ट्रैवलिंग सेल्समैन की समस्या सम्मिलित है, जो सेल्समैन द्वारा लिए गए मार्ग के बारे में पूछती है, और पूर्णांक गुणनखंडन समस्या, जो कारकों की सूची के लिए पूछती है।
अन्य जटिलता वर्गों से संबंध
इच्छानुसार निर्णय समस्या पर विचार करें कक्षा एनपी (जटिलता) में। एनपी की परिभाषा के अनुसार, प्रत्येक समस्या का उदाहरण जिसका उत्तर 'हां' में बहुपद आकार का प्रमाण पत्र है जो 'हां' उत्तर के प्रमाण के रूप में कार्य करता है। इस प्रकार, इन टुपल्स का समुच्चय दी गई फलन समस्या को निरूपित करते हुए संबंध बनाता है में , प्रमाणपत्र प्राप्त करें के लिए . इस फ़ंक्शन समस्या को फ़ंक्शन वेरिएंट कहा जाता है ; यह वर्ग एफएनपी (जटिलता) से संबंधित है।
एफएनपी को एनपी के कार्यात्मक वर्ग एनालॉग के रूप में माना जा सकता है, जिसमें एफएनपी समस्याओं के समाधान कुशलता से हो सकते हैं (अर्थात , इनपुट की लंबाई के संदर्भ में बहुपद समय में) 'सत्यापित, किन्तु आवश्यक नहीं कि कुशलतापूर्वक पाया गया । इसके विपरीत, वर्ग एफपी (जटिलता), जिसे पी के फ़ंक्शन क्लास एनालॉग के रूप में माना जा सकता है, में फ़ंक्शन समस्याएं होती हैं जिनके समाधान बहुपद समय में पाए जा सकते हैं।
स्व-न्यूनीकरण
ध्यान दें कि ऊपर प्रस्तुत की गई एफएसएटी समस्या को सबरूटीन के लिए केवल बहुपद रूप से कई कॉलों का उपयोग करके हल किया जा सकता है जो एसएटी समस्या का फैसला करता है: एल्गोरिदम पहले पूछ सकता है कि क्या सूत्र संतोषजनक है। उसके बाद एल्गोरिथ्म वेरिएबल को ठीक कर सकता है सही करने के लिए और फिर से पूछें। यदि परिणामी सूत्र अभी भी संतोषजनक है तो एल्गोरिथम रहता है सत्य पर नियत है और ठीक करना जारी रखता है , अन्यथा यह तय करता है असत्य होना चाहिए और जारी रहना चाहिए। इस प्रकार, एसएटी का निर्णय लेने वाली ओरेकल मशीन का उपयोग करके बहुपद समय में एफएसएटी हल करने योग्य है। सामान्यतः , एनपी में समस्या को सेल्फ-रिड्यूसिबल कहा जाता है, यदि इसके फलन वेरिएंट को बहुपद समय में मूल समस्या का निर्णय लेने वाले ओरेकल का उपयोग करके हल किया जा सकता है। हर एनपी-पूर्ण समस्या स्व-कम करने योग्य है। यह अनुमान है[by whom?] कि पूर्णांक गुणनखंडन समस्या स्व-कम करने योग्य नहीं है, क्योंकि यह तय करना कि पूर्णांक अभाज्य है या नहीं, पी (आसान) में है,[1] जबकि पूर्णांक गुणनखंडन की समस्या मौलिक कंप्यूटर के लिए कठिन मानी जाती है।
आत्म-कम करने की कई (थोड़ी अलग) धारणाएँ हैं।[2][3][4]
कटौती और पूर्ण समस्याएं
फ़ंक्शन समस्याएं कमी (जटिलता) हो सकती हैं जैसे निर्णय समस्याएं: दी गई फ़ंक्शन समस्याएं और हम कहते हैं कम कर देता है यदि वहाँ बहुपद-समय संगणनीय कार्य उपस्थित हैं और ऐसा कि सभी उदाहरणों के लिए का और संभावित समाधान का , यह मानता है
- यदि है -समाधान, फिर है -समाधान।
इसलिए एनपी-पूर्ण समस्या के अनुरूप एफएनपी-पूर्ण समस्याओं को परिभाषित करना संभव है:
समस्या एफएनपी -पूर्ण है यदि एफएनपी में प्रत्येक समस्या को कम किया जा सकता है . एफएनपी-पूर्ण समस्याओं की जटिलता वर्ग एफएनपी-सी या एफएनपीसी द्वारा दर्शाया गया है। इसलिए समस्या FSAT भी एफएनपी -सम्पूर्ण समस्या है, और यह इसे मानती है यदि और केवल यदि .
कुल कार्य समस्याएं
रिश्ता फ़ंक्शन समस्याओं को परिभाषित करने के लिए उपयोग किए जाने वाले अपूर्ण होने का दोष है: प्रत्येक इनपुट नहीं समकक्ष है ऐसा है कि . इसलिए प्रमाणों की संगणना का प्रश्न उनके अस्तित्व के प्रश्न से अलग नहीं है। इस समस्या को दूर करने के लिए यह सुविधाजनक है कि वर्ग T एफएनपी को एफएनपी के उपवर्ग के रूप में उत्पन्न करने वाले कुल संबंधों के लिए कार्य समस्याओं के प्रतिबंध पर विचार किया जाए। इस वर्ग में कुछ सामरिक खेलों में शुद्ध नैश संतुलन की गणना जैसी समस्याएं सम्मिलित हैं जहां समाधान उपस्थित होने की गारंटी है। इसके अतिरिक्त , यदि T एफएनपी में कोई एफएनपी -सम्पूर्ण समस्या है, तो यह उसका अनुसरण करती है .
यह भी देखें
- निर्णय समस्या
- खोज समस्या
- गिनती की समस्या (जटिलता)
- अनुकूलन समस्या
संदर्भ
- 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.
