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