फंक्शन समस्या: Difference between revisions

Latest revision as of 10:27, 26 November 2023

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

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

कार्यात्मक समस्या $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$ उपयुक्त रूप से एन्कोडेड बूलियन सूत्रों और संतोषजनक असाइनमेंट के टुपल्स द्वारा दिया गया है।

जबकि एसएटी एल्गोरिथम, जिसे $\varphi$ सूत्र दिया गया है, जिसको केवल "असंतोषजनक" या "संतोषजनक" वापस की आवश्यकता होती है, एफएसएटी एल्गोरिथम के पश्चात् वाले स्थिति में कुछ संतोषजनक असाइनमेंट वापस की आवश्यकता होती है।

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

अन्य कॉम्प्लेक्सिटी वर्गों से संबंध

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

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

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

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

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

फ़ंक्शन समस्याओं को निर्णय समस्याओं की तरह कम किया जा सकता है: फ़ंक्शन समस्याओं $\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

↑ 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.

[AKS-1] 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.

[2] Ko, K. (1983). "स्व-रिड्यूसिबिलिटी और कमजोर पी-चयनात्मकता पर". Journal of Computer and System Sciences. 26 (2): 209–221.

[3] Schnorr, C. (1976). "स्व-कम करने योग्य समस्याओं के लिए इष्टतम एल्गोरिदम". In S. Michaelson and R. Milner, editors, Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming: 322–337.

[4] Selman, A. (1988). "प्राकृतिक स्व-रिड्यूसबल सेट". SIAM Journal on Computing. 17 (5): 989–996.

[1]

[2]

[3]

[4]

@@ Line 1: / Line 1: @@
 {{short description|Type of computational problem}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, फ़ंक्शन समस्या [[कम्प्यूटेशनल समस्या]] है जहां प्रत्येक इनपुट के लिए एकल आउटपुट (कुल फ़ंक्शन का) अपेक्षित होता है, लेकिन आउटपुट [[निर्णय समस्या]] की तुलना में अधिक जटिल होता है। फ़ंक्शन समस्याओं के लिए, आउटपुट केवल 'हां' या 'नहीं' नहीं है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत]] में, '''फ़ंक्शन समस्या''' [[कम्प्यूटेशनल समस्या]] है जहां प्रत्येक इनपुट के लिए एकल आउटपुट (कुल फ़ंक्शन का) अपेक्षित होता है, किन्तु आउटपुट [[निर्णय समस्या]] की तुलना में अधिक काम्प्लेक्स होता है। फ़ंक्शन समस्याओं के लिए, आउटपुट केवल 'हां' या 'नहीं' है।
-== औपचारिक परिभाषा ==
+== फार्मल परिभाषा ==
-एक कार्यात्मक समस्या <math>P</math> [[संबंध (गणित)]] द्वारा परिभाषित किया गया है <math>R</math> मनमानी [[वर्णमाला (कंप्यूटर विज्ञान)]] की [[स्ट्रिंग (कंप्यूटर विज्ञान)]] पर <math>\Sigma</math>:
+कार्यात्मक समस्या <math>P</math> को अर्बिट्ररी वर्णमाला <math>\Sigma</math> की स्ट्रिंग पर संबंध <math>R</math> द्वारा परिभाषित किया गया है
 : <math>R \subseteq \Sigma^* \times \Sigma^*.</math>
-एक एल्गोरिदम हल करता है <math>P</math> यदि प्रत्येक इनपुट के लिए <math>x</math> ऐसा है कि वहाँ मौजूद है <math>y</math> संतुष्टि देने वाला <math>(x, y) \in R</math>, एल्गोरिदम ऐसा उत्पन्न करता है <math>y</math>, और यदि ऐसा कोई नहीं है <math>y</math>, यह अस्वीकार करता है।
+इस प्रकार यह एल्गोरिथ्म <math>P</math> को हल करता है यदि प्रत्येक इनपुट <math>x</math> के लिए जैसे कि R में संतोषजनक <math>(x, y) \in R</math> उपस्थित है, तो एल्गोरिदम ऐसा <math>y</math> उत्पन्न करता है, और यदि ऐसा कोई <math>y</math> नहीं है, तो यह अस्वीकार कर देता है।
-एक वादा फ़ंक्शन समस्या को कुछ भी करने की अनुमति है (इस प्रकार समाप्त नहीं हो सकती) यदि ऐसा नहीं है <math>y</math> मौजूद।
+यदि ऐसा कोई <math>y</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>\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>\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>L</math> पर विचार करें। एनपी की परिभाषा के अनुसार, प्रत्येक समस्या उदाहरण <math>x</math> जिसका उत्तर 'हां' है, जिसमें बहुपद-आकार प्रमाणपत्र <math>y</math> है जो 'हां' उत्तर के लिए प्रमाण के रूप में कार्य करता है। इस प्रकार, इन टुपल्स <math>(x,y)</math> का सेट ऐसा संबंध बनाता है, जो कि "<math>L</math> में <math>x</math> दिए गये  फ़ंक्शन समस्या का प्रतिनिधित्व करता है तथा जहाँ  <math>x</math> के लिए प्रमाणपत्र <math>y</math> खोजे जाता है। और इस फ़ंक्शन समस्या को L का फ़ंक्शन वैरिएंट भी कहा जाता है; यह एफएनपी वर्ग से संबंधित है।
+एफएनपी को एनपी के फ़ंक्शन क्लास एनालॉग के रूप में सोचा जा सकता है, जिसमें एफएनपी समस्याओं का समाधान कुशलतापूर्वक (अर्थात, इनपुट की लंबाई के संदर्भ में बहुपद समय में) ''सत्यापित'' किया जा सकता है, किन्तु आवश्यक नहीं कि कुशलतापूर्वक ''पाया'' जा सकता है। इसके विपरीत, वर्ग [[एफपी (जटिलता)|एफपी (कॉम्प्लेक्सिटी)]], जिसे p के फ़ंक्शन क्लास एनालॉग के रूप में सोचा जा सकता है, जिसमें फ़ंक्शन समस्याएं सम्मिलित हैं जिनके समाधान बहुपद समय में पाए जा सकते हैं।
 == स्व-रिड्यूसिबिलिटी ==
-ध्यान दें कि ऊपर पेश की गई एफएसएटी समस्या को सबरूटीन में केवल बहुपद रूप से कई कॉल का उपयोग करके हल किया जा सकता है जो एसएटी समस्या का निर्णय लेता है: एल्गोरिदम पहले पूछ सकता है कि क्या सूत्र <math>\varphi</math> संतोषजनक है. उसके बाद एल्गोरिदम वेरिएबल को ठीक कर सकता है <math>x_1</math> सत्य करें और दोबारा पूछें। यदि परिणामी सूत्र अभी भी संतोषजनक है तो एल्गोरिथम रखता है <math>x_1</math> TRUE पर स्थिर किया गया और ठीक करना जारी रखा गया <math>x_2</math>, अन्यथा यह निर्णय लेता है <math>x_1</math> गलत होना चाहिए और जारी रहेगा। इस प्रकार, एफएसएटी को [[ओरेकल मशीन]] का उपयोग करके एसएटी का निर्णय लेने के लिए बहुपद समय में हल किया जा सकता है। सामान्य तौर पर, एनपी में समस्या को ''सेल्फ-रिड्यूसिबल'' कहा जाता है, यदि इसके फ़ंक्शन संस्करण को मूल समस्या का निर्णय लेने वाले दैवज्ञ का उपयोग करके बहुपद समय में हल किया जा सकता है। प्रत्येक एनपी-पूर्ण समस्या स्वयं-कम करने योग्य है। यह अनुमान लगाया गया है {{By whom|date=February 2020}} कि पूर्णांक गुणनखंडन समस्या स्वतः कम करने योग्य नहीं है, क्योंकि यह निर्णय लेना कि कोई पूर्णांक अभाज्य है या नहीं, 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>
-== कटौती और संपूर्ण समस्याएँ ==
+ध्यान दें कि ऊपर प्रस्तुत की गई एफएसएटी समस्या को सबरूटीन में केवल बहुपद रूप से अनेक कॉल का उपयोग करके हल किया जा सकता है जो एसएटी समस्या का निर्णय लेता है: एल्गोरिदम पहले पूछ सकता है कि सूत्र <math>\varphi</math> संतोषजनक है या नहीं। उसके बाद एल्गोरिदम वेरिएबल <math>x_1</math> को TRUE पर ठीक कर सकता है और फिर से पूछ सकता है। यदि परिणामी सूत्र अभी भी संतोषजनक है तो एल्गोरिदम <math>x_1</math> को is पर स्थिर रखता है और <math>x_2</math> को ठीक करना जारी रखता है, अन्यथा यह निर्णय लेता है कि <math>x_1</math> को FALSE होना चाहिए और जारी रहता है। इस प्रकार, एफएसएटी ओरेकल निर्णय लेने वाले एसएटी का उपयोग करके बहुपद समय में हल करने योग्य है। सामान्यतः एनपी में समस्या को स्व-रिड्यूसिबल कहा जाता है यदि इसके फ़ंक्शन संस्करण को मूल समस्या का निर्णय लेने वाले ओरेकल का उपयोग करके बहुपद समय में हल किया जा सकता है। प्रत्येक एनपी-पूर्ण समस्या स्वयं-कम करने योग्य है। यह अनुमान लगाया गया है [किसके द्वारा?] कि पूर्णांक गुणनखंडन समस्या स्व-घटाने योग्य नहीं है, क्योंकि यह तय करना कि पूर्णांक अभाज्य है या नहीं, 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>
-फ़ंक्शन समस्याएं निर्णय समस्याओं की तरह ही [[कमी (जटिलता)]] हो सकती हैं: फ़ंक्शन समस्याएं दी गई हैं <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>R</math> के सभी उदाहरणों <math>x</math> और संभावित समाधान <math>y</math> के लिए एस का यह मानना है
-*अगर <math>x</math> है <math>R</math>-समाधान, फिर <math>f(x)</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>\Pi_R</math> यदि एफएनपी में प्रत्येक समस्या को कम किया जा सकता है तो एफएनपी-पूर्ण है जो <math>\Pi_R</math>. एफएनपी-पूर्ण समस्याओं की काम्प्लेक्स वर्ग को एफएनपी-सी या एफएनपीसी द्वारा दर्शाया जाता है। इसलिए समस्या एफएसएटी भी एफएनपी-पूर्ण समस्या है, और यह ऐसा मानती है <math>\mathbf{P} = \mathbf{NP}</math> यदि और केवल यदि <math>\mathbf{FP} = \mathbf{FNP}</math>.है
-एक समस्या <math>\Pi_R</math> यदि एफएनपी में प्रत्येक समस्या को कम किया जा सकता है तो एफएनपी-पूर्ण है <math>\Pi_R</math>. एफएनपी-पूर्ण समस्याओं की जटिलता वर्ग को एफएनपी-सी या एफएनपीसी द्वारा दर्शाया जाता है। इसलिए समस्या एफएसएटी भी एफएनपी-पूर्ण समस्या है, और यह ऐसा मानती है <math>\mathbf{P} = \mathbf{NP}</math> अगर और केवल अगर <math>\mathbf{FP} = \mathbf{FNP}</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>. इसलिए प्रमाणों की संगणना का प्रश्न उनके अस्तित्व के प्रश्न से अलग नहीं है। इस समस्या को दूर करने के लिए फ़ंक्शन समस्याओं को एफएनपी के उपवर्ग के रूप में वर्ग [[टीएफएनपी]] उत्पन्न करने वाले कुल संबंधों तक सीमित करने पर विचार करना सुविधाजनक है। इस वर्ग में कुछ रणनीतिक खेलों में शुद्ध [[नैश संतुलन]] की गणना जैसी समस्याएं शामिल हैं जहां समाधान मौजूद होने की गारंटी है। इसके अलावा, यदि टीएफएनपी में कोई एफएनपी-पूर्ण समस्या है तो यह उसका अनुसरण करता है <math>\mathbf{NP} = \textbf{co-NP}</math>.
+फ़ंक्शन समस्याओं को परिभाषित करने के लिए उपयोग किए जाने वाले संबंध <math>R(x, y)</math> में अपूर्ण होने का दोष है। प्रत्येक इनपुट <math>x</math> में समकक्ष <math>y</math> नहीं होता है जैसे कि <math>(x, y) \in R</math> इसलिए प्रमाणों की संगणना का प्रश्न इससे भिन्न नहीं है उनके अस्तित्व का प्रश्न. इस समस्या को दूर करने के लिए फ़ंक्शन समस्याओं को एफएनपी के उपवर्ग के रूप में वर्ग टीएफएनपी उत्पन्न करने वाले कुल संबंधों तक सीमित करने पर विचार करना सुविधाजनक है। इस वर्ग में कुछ रणनीतिक खेलों में शुद्ध नैश संतुलन की गणना जैसी समस्याएं सम्मिलित हैं जहां समाधान उपस्थित होने की गारंटी है। इसके अतिरिक्त, यदि टीएफएनपी में कोई एफएनपी-पूर्ण समस्या है तो यह उसका अनुसरण <math>\mathbf{NP} = \textbf{co-NP}</math> करता है
 ==यह भी देखें==
 *निर्णय समस्या
 *[[खोज समस्या]]
-*[[गिनती की समस्या (जटिलता)]]
+*[[गिनती की समस्या (जटिलता)|गणना की समस्या (कॉम्प्लेक्सिटी)]]
 *[[अनुकूलन समस्या]]
@@ Line 59: / Line 58: @@
 [[Category: Machine Translated Page]]
 [[Category:Created On 25/07/2023]]
+[[Category:Vigyan Ready]]

Anonymous

Search

फंक्शन समस्या: Difference between revisions

Namespaces

More

Page actions

Latest revision as of 10:27, 26 November 2023

Contents

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

उदाहरण

अन्य कॉम्प्लेक्सिटी वर्गों से संबंध

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

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

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

यह भी देखें

संदर्भ

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

फंक्शन समस्या: Difference between revisions

Latest revision as of 10:27, 26 November 2023

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

उदाहरण

अन्य कॉम्प्लेक्सिटी वर्गों से संबंध

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

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

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

यह भी देखें

संदर्भ

Navigation

Wiki tools

Page tools

Other projects

Categories