एफपी (कॉम्प्लेक्सिटी): Difference between revisions
From Vigyanwiki
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Complexity class}} | {{Short description|Complexity class}} | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में | [[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत]] में [[जटिलता वर्ग|कॉम्प्लेक्सिटी क्लास]] '''एफपी''' फ़ंक्शन समस्याओं का समूह है जिसे पोलिनोमिअल-टाइम में एक [[नियतात्मक ट्यूरिंग मशीन|डेटर्मिनिस्टिक ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है। सामान्यतः यह [[निर्णय समस्या|समस्या]] क्लास [[पी (जटिलता)|P]] के एक फ़ंक्शन समस्या का संस्करण है। यह समस्या उस फ़ंक्शन का क्लास है जिसकी यादृच्छिक रूप से प्रारम्भिक कंप्यूटर पर कुशलतापूर्वक गणना की जा सकती है। | ||
एफपी और | एफपी और 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> | :एक [[द्विआधारी संबंध|बाइनरी संबंध]] <math>P(x,y)</math> एफपी में है यदि और केवल यदि कोई डेटर्मिनिस्टिक पोलिनोमिअल-टाइम एल्गोरिदम है जहां <math>x</math> दिया गया है और <math>y</math> के मान के लिए <math>P(x,y)</math> मे स्थित है जो संकेत देता है कि इसमे कोई भी <math>y</math> सम्मिलित नहीं है। | ||
==संबंधित जटिलता वर्ग== | ==संबंधित [[जटिलता वर्ग|कॉम्प्लेक्सिटी क्लास]]== | ||
* एफएनपी | * एफएनपी बाइनरी संबंधों का समूह है जिसके लिए एक पोलिनोमिअल-टाइम एल्गोरिथ्म है जो 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 बराबर हैं।
संदर्भ
- ↑ Bürgisser, Peter (2000). बीजगणितीय जटिलता सिद्धांत में पूर्णता और कमी. Algorithms and Computation in Mathematics. Vol. 7. Berlin: Springer-Verlag. p. 66. ISBN 3-540-66752-0. Zbl 0948.68082.
- ↑ 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.
