फंक्शन समस्या

कम्प्यूटेशनल जटिलता सिद्धांत में, फ़ंक्शन समस्या कम्प्यूटेशनल समस्या है जहां प्रत्येक इनपुट के लिए एकल आउटपुट (कुल फ़ंक्शन का) अपेक्षित होता है, लेकिन आउटपुट निर्णय समस्या की तुलना में अधिक जटिल होता है। फ़ंक्शन समस्याओं के लिए, आउटपुट केवल 'हां' या 'नहीं' नहीं है।

औपचारिक परिभाषा

एक कार्यात्मक समस्या $P$ संबंध (गणित) द्वारा परिभाषित किया गया है $R$ मनमानी वर्णमाला (कंप्यूटर विज्ञान) की स्ट्रिंग (कंप्यूटर विज्ञान) पर $\Sigma$:

$R\subseteq \Sigma ^{*}\times \Sigma ^{*}.$

एक एल्गोरिदम हल करता है $P$ यदि प्रत्येक इनपुट के लिए $x$ ऐसा है कि वहाँ मौजूद है $y$ संतुष्टि देने वाला $(x,y)\in R$, एल्गोरिदम ऐसा उत्पन्न करता है $y$, और यदि ऐसा कोई नहीं है $y$, यह अस्वीकार करता है।

एक वादा फ़ंक्शन समस्या को कुछ भी करने की अनुमति है (इस प्रकार समाप्त नहीं हो सकती) यदि ऐसा नहीं है $y$ मौजूद।

उदाहरण

एक प्रसिद्ध फ़ंक्शन समस्या कार्यात्मक बूलियन संतुष्टि समस्या, संक्षेप में एफएसएटी द्वारा दी गई है। समस्या, जो बूलियन संतुष्टि समस्या निर्णय समस्या से निकटता से संबंधित है, को निम्नानुसार तैयार किया जा सकता है:

एक बूलियन सूत्र दिया गया $\varphi$ चर के साथ $x_{1},\ldots ,x_{n}$, असाइनमेंट ढूंढें $x_{i}\rightarrow \{{\text{TRUE}},{\text{FALSE}}\}$ ऐसा है कि $\varphi$ का मूल्यांकन करता है ${\text{TRUE}}$ या तय करें कि ऐसा कोई असाइनमेंट मौजूद नहीं है।

इस मामले में संबंध $R$ उपयुक्त रूप से एन्कोडेड बूलियन फ़ार्मुलों और संतोषजनक असाइनमेंट के टुपल्स द्वारा दिया गया है। जबकि SAT एल्गोरिथ्म, सूत्र के साथ खिलाया $\varphi$, केवल असंतोषजनक या संतोषजनक लौटने की जरूरत है, एफएसएटी एल्गोरिथ्म को बाद वाले मामले में कुछ संतोषजनक असाइनमेंट लौटाने की जरूरत है।

अन्य उल्लेखनीय उदाहरणों में ट्रैवलिंग सेल्समैन की समस्या शामिल है, जो सेल्समैन द्वारा अपनाए गए मार्ग के बारे में पूछती है, और पूर्णांक गुणनखंडन समस्या, जो कारकों की सूची मांगती है।

अन्य जटिलता वर्गों से संबंध

एक मनमाना निर्णय समस्या पर विचार करें $L$ कक्षा एनपी (जटिलता) में। एनपी की परिभाषा के अनुसार, प्रत्येक समस्या का उदाहरण $x$ जिसका उत्तर 'हां' है, उसके पास बहुपद-आकार का प्रमाणपत्र है $y$ जो 'हाँ' उत्तर के लिए प्रमाण के रूप में कार्य करता है। इस प्रकार, इन टुपल्स का सेट $(x,y)$ दिए गए फ़ंक्शन समस्या का प्रतिनिधित्व करते हुए संबंध बनाता है $x$ में $L$, प्रमाणपत्र खोजें $y$ के लिए $x$. इस फ़ंक्शन समस्या को फ़ंक्शन वैरिएंट कहा जाता है $L$; यह एफएनपी (जटिलता) वर्ग से संबंधित है।

एफएनपी को एनपी के फ़ंक्शन क्लास एनालॉग के रूप में सोचा जा सकता है, जिसमें एफएनपी समस्याओं का समाधान कुशलतापूर्वक (यानी, इनपुट की लंबाई के संदर्भ में बहुपद समय में) सत्यापित किया जा सकता है, लेकिन जरूरी नहीं कि कुशलतापूर्वक पाया जा सके। इसके विपरीत, वर्ग एफपी (जटिलता), जिसे पी के फ़ंक्शन क्लास एनालॉग के रूप में सोचा जा सकता है, में फ़ंक्शन समस्याएं शामिल हैं जिनके समाधान बहुपद समय में पाए जा सकते हैं।

स्व-रिड्यूसिबिलिटी

ध्यान दें कि ऊपर पेश की गई एफएसएटी समस्या को सबरूटीन में केवल बहुपद रूप से कई कॉल का उपयोग करके हल किया जा सकता है जो एसएटी समस्या का निर्णय लेता है: एल्गोरिदम पहले पूछ सकता है कि क्या सूत्र $\varphi$ संतोषजनक है. उसके बाद एल्गोरिदम वेरिएबल को ठीक कर सकता है $x_{1}$ सत्य करें और दोबारा पूछें। यदि परिणामी सूत्र अभी भी संतोषजनक है तो एल्गोरिथम रखता है $x_{1}$ TRUE पर स्थिर किया गया और ठीक करना जारी रखा गया $x_{2}$, अन्यथा यह निर्णय लेता है $x_{1}$ गलत होना चाहिए और जारी रहेगा। इस प्रकार, एफएसएटी को ओरेकल मशीन का उपयोग करके एसएटी का निर्णय लेने के लिए बहुपद समय में हल किया जा सकता है। सामान्य तौर पर, एनपी में समस्या को सेल्फ-रिड्यूसिबल कहा जाता है, यदि इसके फ़ंक्शन संस्करण को मूल समस्या का निर्णय लेने वाले दैवज्ञ का उपयोग करके बहुपद समय में हल किया जा सकता है। प्रत्येक एनपी-पूर्ण समस्या स्वयं-कम करने योग्य है। यह अनुमान लगाया गया है कि पूर्णांक गुणनखंडन समस्या स्वतः कम करने योग्य नहीं है, क्योंकि यह निर्णय लेना कि कोई पूर्णांक अभाज्य है या नहीं, P में है (आसान), जबकि पूर्णांक गुणनखंडन समस्या को शास्त्रीय कंप्यूटर के लिए कठिन माना जाता है। स्व-रिड्यूसिबिलिटी की कई (थोड़ी भिन्न) धारणाएँ हैं।

कटौती और संपूर्ण समस्याएँ

फ़ंक्शन समस्याएं निर्णय समस्याओं की तरह ही कमी (जटिलता) हो सकती हैं: फ़ंक्शन समस्याएं दी गई हैं $\Pi _{R}$ और $\Pi _{S}$ हम ऐसा कहते हैं $\Pi _{R}$ तक कम कर देता है $\Pi _{S}$ यदि बहुपद-समय गणना योग्य फ़ंक्शन मौजूद हैं $f$ और $g$ ऐसा सभी उदाहरणों के लिए $x$ का $R$ और संभावित समाधान $y$ का $S$, यह उसे धारण करता है

• अगर $x$ है $R$-समाधान, फिर $f(x)$ है $S$-समाधान।
• $(f(x),y)\in S\implies (x,g(x,y))\in R.$

इसलिए एफएनपी-पूर्ण समस्याओं को एनपी-पूर्ण समस्या के अनुरूप परिभाषित करना संभव है:

एक समस्या $\Pi _{R}$ यदि एफएनपी में प्रत्येक समस्या को कम किया जा सकता है तो एफएनपी-पूर्ण है $\Pi _{R}$. एफएनपी-पूर्ण समस्याओं की जटिलता वर्ग को एफएनपी-सी या एफएनपीसी द्वारा दर्शाया जाता है। इसलिए समस्या एफएसएटी भी एफएनपी-पूर्ण समस्या है, और यह ऐसा मानती है $\mathbf {P} =\mathbf {NP}$ अगर और केवल अगर $\mathbf {FP} =\mathbf {FNP}$.

कुल फ़ंक्शन समस्याएँ

रिश्ता $R(x,y)$ फ़ंक्शन समस्याओं को परिभाषित करने के लिए उपयोग किए जाने वाले अपूर्ण होने का दोष है: प्रत्येक इनपुट नहीं $x$ समकक्ष है $y$ ऐसा है कि $(x,y)\in R$. इसलिए प्रमाणों की संगणना का प्रश्न उनके अस्तित्व के प्रश्न से अलग नहीं है। इस समस्या को दूर करने के लिए फ़ंक्शन समस्याओं को एफएनपी के उपवर्ग के रूप में वर्ग टीएफएनपी उत्पन्न करने वाले कुल संबंधों तक सीमित करने पर विचार करना सुविधाजनक है। इस वर्ग में कुछ रणनीतिक खेलों में शुद्ध नैश संतुलन की गणना जैसी समस्याएं शामिल हैं जहां समाधान मौजूद होने की गारंटी है। इसके अलावा, यदि टीएफएनपी में कोई एफएनपी-पूर्ण समस्या है तो यह उसका अनुसरण करता है $\mathbf {NP} ={\textbf {co-NP}}$.

यह भी देखें

• निर्णय समस्या
• खोज समस्या
• गिनती की समस्या (जटिलता)
• अनुकूलन समस्या

संदर्भ

• 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