एफपी (कॉम्प्लेक्सिटी): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{Short description|Complexity class}}
{{Short description|Complexity class}}
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, [[जटिलता वर्ग]] '''एफपी''' फ़ंक्शन समस्याओं का सेट है जिसे बहुपद समय में एक [[नियतात्मक ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है। यह [[निर्णय समस्या]] वर्ग [[पी (जटिलता)]] का फ़ंक्शन समस्या संस्करण है। सामान्यतः यह उन कार्यों का वर्ग है जिन्हें यादृच्छिककरण के बिना शास्त्रीय कंप्यूटर पर कुशलतापूर्वक गणना की जा सकती है।
[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत]] में [[जटिलता वर्ग|कॉम्प्लेक्सिटी क्लास]] '''एफपी''' फ़ंक्शन समस्याओं का समूह है जिसे पोलिनोमिअल-टाइम में एक [[नियतात्मक ट्यूरिंग मशीन|डेटर्मिनिस्टिक ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है। सामान्यतः यह [[निर्णय समस्या|समस्या]] क्लास [[पी (जटिलता)|P]] के एक फ़ंक्शन समस्या का संस्करण है। यह समस्या उस फ़ंक्शन का क्लास है जिसकी यादृच्छिक रूप से प्रारम्भिक कंप्यूटर पर कुशलतापूर्वक गणना की जा सकती है।


एफपी और पी के बीच अंतर यह है कि पी में समस्याओं का उत्तर एक-बिट, हां/नहीं में होता है, जबकि एफपी में समस्याओं का कोई भी आउटपुट हो सकता है जिसकी गणना बहुपद समय में की जा सकती है। उदाहरण के लिए, दो संख्याओं को जोड़ना एक एफपी समस्या है, जबकि यह निर्धारित करना कि उनका योग विषम है या नहीं, पी में है।<ref>{{cite book | last=Bürgisser | first=Peter | title=बीजगणितीय जटिलता सिद्धांत में पूर्णता और कमी| zbl=0948.68082 | series=Algorithms and Computation in Mathematics | volume=7 | location=Berlin | publisher=[[Springer-Verlag]] | year=2000 | isbn=3-540-66752-0 | page=66 }}</ref> बहुपद-समय फ़ंक्शन समस्याएं बहुपद-समय कटौती को परिभाषित करने में मौलिक हैं, जिनका उपयोग एनपी-पूर्ण समस्याओं के वर्ग को परिभाषित करने के लिए किया जाता है।<ref>{{cite book | first=Elaine | last=Rich |author-link=Elaine Rich| title=Automata, computability and complexity: theory and applications | publisher=Prentice Hall | year=2008 | isbn=0-13-228806-0 | chapter=28.10 "The problem classes FP and FNP" | pages=689–694 | url=http://www.theoryandapplications.org/ }}</ref>
एफपी और P के बीच अंतर यह है कि P में समस्याओं का उत्तर एक बिट (हां/नहीं) में होता है, जबकि एफपी में समस्याओं का कोई भी आउटपुट हो सकता है जिसकी गणना पोलिनोमिअल-टाइम में की जा सकती है। उदाहरण के लिए दो संख्याओं को जोड़ना एक एफपी समस्या है, जबकि यह निर्धारित करना कि उनका योग विषम है या नहीं यह P की मूल समस्या है।<ref>{{cite book | last=Bürgisser | first=Peter | title=बीजगणितीय जटिलता सिद्धांत में पूर्णता और कमी| zbl=0948.68082 | series=Algorithms and Computation in Mathematics | volume=7 | location=Berlin | publisher=[[Springer-Verlag]] | year=2000 | isbn=3-540-66752-0 | page=66 }}</ref> पोलिनोमिअल-टाइम फ़ंक्शन समस्याएं पोलिनोमिअल-टाइम रिडक्शन को परिभाषित करने के लिए मुख्य हैं। जिनका उपयोग एनपी-कॉम्प्लेटनेस समस्याओं की क्लास को परिभाषित करने के लिए किया जाता है।<ref>{{cite book | first=Elaine | last=Rich |author-link=Elaine Rich| title=Automata, computability and complexity: theory and applications | publisher=Prentice Hall | year=2008 | isbn=0-13-228806-0 | chapter=28.10 "The problem classes FP and FNP" | pages=689–694 | url=http://www.theoryandapplications.org/ }}</ref>
==औपचारिक परिभाषा==
==औपचारिक परिभाषा==
एफपी को औपचारिक रूप से इस प्रकार परिभाषित किया गया है:
एफपी को औपचारिक रूप से इस प्रकार परिभाषित किया गया है:


:एक [[द्विआधारी संबंध]] <math>P(x,y)</math> FP में है यदि और केवल यदि कोई नियतात्मक बहुपद समय एल्गोरिदम है, जो <math>x</math> दिया गया है, या तो कुछ <math>y</math> पाता है जैसे कि <math>P(x,y)</math> रखता है, या संकेत देता है कि ऐसा कोई <math>y</math> मौजूद नहीं है।
:एक [[द्विआधारी संबंध|बाइनरी संबंध]] <math>P(x,y)</math> एफपी में है यदि और केवल यदि कोई डेटर्मिनिस्टिक पोलिनोमिअल-टाइम एल्गोरिदम है जहां <math>x</math> दिया गया है और <math>y</math> के मान के लिए <math>P(x,y)</math> मे स्थित है जो संकेत देता है कि इसमे कोई भी <math>y</math> सम्मिलित नहीं है।


==संबंधित जटिलता वर्ग==
==संबंधित [[जटिलता वर्ग|कॉम्प्लेक्सिटी क्लास]]==


* एफएनपी द्विआधारी संबंधों का सेट है जिसके लिए एक बहुपद समय एल्गोरिथ्म है, जो x और y दिए जाने पर जांच करता है कि P(x,y) कायम है या नहीं। जिस प्रकार पी और एफपी आपस में घनिष्ठ रूप से संबंधित हैं, उसी प्रकार एनपी एफएनपी से घनिष्ठ रूप से संबंधित है। एफपी = एफएनपी यदि और केवल यदि पी = एनपी।
* एफएनपी बाइनरी संबंधों का समूह है जिसके लिए एक पोलिनोमिअल-टाइम एल्गोरिथ्म है जो x और y का मान दिए जाने पर जांच करता है कि P(x,y) स्थित है या नहीं स्थित है जिस प्रकार P और एफपी आपस में घनिष्ठ (क्लोसली) रूप से संबंधित हैं। उसी प्रकार <code>NP</code> भी <code>FNP,</code> <code>FP = FNP</code> और <code>P = NP</code>से अधिक निकटता से संबंधित है। <code>'''FL''' = '''FP'''</code>
* क्योंकि एक मशीन जो लॉगरिदमिक स्पेस का उपयोग करती है, उसमें बहुपद रूप से कई कॉन्फ़िगरेशन होते हैं, एफएल, फ़ंक्शन समस्याओं का सेट जिसे लॉगस्पेस में गणना की जा सकती है, एफपी में निहित है। यह ज्ञात नहीं है कि एफएल = एफपी; यह यह निर्धारित करने की समस्या के अनुरूप है कि निर्णय वर्ग पी और एल बराबर हैं या नहीं।
* क्योंकि एक मशीन जो लॉगरिदमिक स्पेस का उपयोग करती है और उसमें पोलिनोमिअल रूप से कई कॉन्फ़िगरेशन होते हैं जिसमे एफएल फ़ंक्शन समस्याओं का समूह जिसे लॉगस्पेस में गणना की जा सकती है, एफपी में निहित है। लेकिन यह ज्ञात नहीं है कि <code>'''FL = FP'''</code> यह निर्धारित करने की समस्या के अनुरूप है कि डिसिजन-क्लास P और L बराबर हैं।


==संदर्भ==
==संदर्भ==

Revision as of 12:09, 7 August 2023

कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत में कॉम्प्लेक्सिटी क्लास एफपी फ़ंक्शन समस्याओं का समूह है जिसे पोलिनोमिअल-टाइम में एक डेटर्मिनिस्टिक ट्यूरिंग मशीन द्वारा हल किया जा सकता है। सामान्यतः यह समस्या क्लास P के एक फ़ंक्शन समस्या का संस्करण है। यह समस्या उस फ़ंक्शन का क्लास है जिसकी यादृच्छिक रूप से प्रारम्भिक कंप्यूटर पर कुशलतापूर्वक गणना की जा सकती है।

एफपी और P के बीच अंतर यह है कि P में समस्याओं का उत्तर एक बिट (हां/नहीं) में होता है, जबकि एफपी में समस्याओं का कोई भी आउटपुट हो सकता है जिसकी गणना पोलिनोमिअल-टाइम में की जा सकती है। उदाहरण के लिए दो संख्याओं को जोड़ना एक एफपी समस्या है, जबकि यह निर्धारित करना कि उनका योग विषम है या नहीं यह P की मूल समस्या है।[1] पोलिनोमिअल-टाइम फ़ंक्शन समस्याएं पोलिनोमिअल-टाइम रिडक्शन को परिभाषित करने के लिए मुख्य हैं। जिनका उपयोग एनपी-कॉम्प्लेटनेस समस्याओं की क्लास को परिभाषित करने के लिए किया जाता है।[2]

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

एफपी को औपचारिक रूप से इस प्रकार परिभाषित किया गया है:

एक बाइनरी संबंध एफपी में है यदि और केवल यदि कोई डेटर्मिनिस्टिक पोलिनोमिअल-टाइम एल्गोरिदम है जहां दिया गया है और के मान के लिए मे स्थित है जो संकेत देता है कि इसमे कोई भी सम्मिलित नहीं है।

संबंधित कॉम्प्लेक्सिटी क्लास

  • एफएनपी बाइनरी संबंधों का समूह है जिसके लिए एक पोलिनोमिअल-टाइम एल्गोरिथ्म है जो x और y का मान दिए जाने पर जांच करता है कि P(x,y) स्थित है या नहीं स्थित है जिस प्रकार P और एफपी आपस में घनिष्ठ (क्लोसली) रूप से संबंधित हैं। उसी प्रकार NP भी FNP, FP = FNP और P = NPसे अधिक निकटता से संबंधित है। FL = FP
  • क्योंकि एक मशीन जो लॉगरिदमिक स्पेस का उपयोग करती है और उसमें पोलिनोमिअल रूप से कई कॉन्फ़िगरेशन होते हैं जिसमे एफएल फ़ंक्शन समस्याओं का समूह जिसे लॉगस्पेस में गणना की जा सकती है, एफपी में निहित है। लेकिन यह ज्ञात नहीं है कि FL = FP यह निर्धारित करने की समस्या के अनुरूप है कि डिसिजन-क्लास P और L बराबर हैं।

संदर्भ

  1. Bürgisser, Peter (2000). बीजगणितीय जटिलता सिद्धांत में पूर्णता और कमी. Algorithms and Computation in Mathematics. Vol. 7. Berlin: Springer-Verlag. p. 66. ISBN 3-540-66752-0. Zbl 0948.68082.
  2. Rich, Elaine (2008). "28.10 "The problem classes FP and FNP"". Automata, computability and complexity: theory and applications. Prentice Hall. pp. 689–694. ISBN 0-13-228806-0.


बाहरी संबंध