एफपी (कॉम्प्लेक्सिटी)
कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत में कॉम्प्लेक्सिटी क्लास एफपी फ़ंक्शन समस्याओं की एक क्लास है जिसे पोलिनोमिअल-टाइम में एक डेटर्मिनिस्टिक ट्यूरिंग मशीन द्वारा हल किया जा सकता है। सामान्यतः यह समस्या क्लास P के एक फ़ंक्शन समस्या का संस्करण है। यह समस्या उस फ़ंक्शन की क्लास है जिसकी यादृच्छिक रूप से प्रारम्भिक कंप्यूटर पर कुशलतापूर्वक गणना की जा सकती है।
एफपी और P के बीच अंतर यह है कि P में समस्याओं का उत्तर एक बिट (हां/नहीं) में होता है, जबकि एफपी में समस्याओं का कोई भी आउटपुट हो सकता है जिसकी गणना पोलिनोमिअल-टाइम में की जा सकती है। उदाहरण के लिए दो संख्याओं को जोड़ना एक एफपी समस्या है, जबकि यह निर्धारित करना कि उनका योग विषम है या नहीं यह P की मूल समस्या है।[1] पोलिनोमिअल-टाइम फ़ंक्शन समस्याएं पोलिनोमिअल-टाइम रिडक्शन को परिभाषित करने के लिए मुख्य हैं। जिनका उपयोग एनपी-कॉम्प्लेटनेस समस्याओं की क्लास को परिभाषित करने के लिए किया जाता है।[2]
औपचारिक परिभाषा
एफपी को औपचारिक रूप से इस प्रकार परिभाषित किया गया है:
- एक बाइनरी संबंध एफपी में है यदि और केवल यदि कोई डेटर्मिनिस्टिक पोलिनोमिअल-टाइम एल्गोरिदम है जहां दिया गया है और के मान के लिए मे स्थित है जो संकेत देता है कि इसमे कोई भी सम्मिलित नहीं है।
संबंधित कॉम्प्लेक्सिटी क्लास
- एफएनपी बाइनरी संबंधों का समूह है जिसके लिए एक पोलिनोमिअल-टाइम एल्गोरिथ्म है जो x और y का मान दिए जाने पर जांच करता है कि P(x,y) स्थित है या नहीं स्थित है, जिस प्रकार P और एफपी आपस में घनिष्ठ (क्लोसली) रूप से संबंधित हैं। उसी प्रकार
NPभीFNP,FP = FNPऔरP = NPसे अधिक निकटता से संबंधित है। - क्योंकि एक मशीन जो लॉगरिदमिक स्पेस का उपयोग करती है और उसमें पोलिनोमिअल रूप से कई कॉन्फ़िगरेशन होते हैं जिसमे एफएल फ़ंक्शन समस्याओं का एक समूह जिसकी लॉगस्पेस में गणना की जा सकती है, एफपी में निहित है। लेकिन यह ज्ञात नहीं है कि
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.
