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

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

फार्मल परिभाषा

कार्यात्मक समस्या $P$ को एक अर्बिट्ररी वर्णमाला $\Sigma$ की स्ट्रिंग पर एक संबंध $R$ द्वारा परिभाषित किया गया है

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

एक एल्गोरिथ्म $P$ को हल करता है यदि प्रत्येक इनपुट $x$ के लिए जैसे कि R में संतोषजनक $(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)$ का सेट एक संबंध बनाता है, जो फ़ंक्शन समस्या का प्रतिनिधित्व करता है "$L$ में $x$ दिया गया है, $x$ के लिए एक प्रमाणपत्र $y$ खोजे"। इस फ़ंक्शन समस्या को L का फ़ंक्शन वैरिएंट कहा जाता है; यह एफएनपी वर्ग से संबंधित है।

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

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

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

रिडक्सन और संपूर्ण समस्याएँ

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

• यदि $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}$.

एक समस्या $\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