एफपी (कॉम्प्लेक्सिटी)

कम्प्यूटेशनल जटिलता सिद्धांत में, जटिलता वर्ग एफपी फ़ंक्शन समस्याओं का सेट है जिसे बहुपद समय में एक नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है। यह निर्णय समस्या वर्ग पी (जटिलता) का फ़ंक्शन समस्या संस्करण है। सामान्यतः यह उन कार्यों का वर्ग है जिन्हें यादृच्छिककरण के बिना शास्त्रीय कंप्यूटर पर कुशलतापूर्वक गणना की जा सकती है।

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

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

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

एक द्विआधारी संबंध $P(x,y)$ FP में है यदि और केवल यदि कोई नियतात्मक बहुपद समय एल्गोरिदम है, जो $x$ दिया गया है, या तो कुछ $y$ पाता है जैसे कि $P(x,y)$ रखता है, या संकेत देता है कि ऐसा कोई $y$ मौजूद नहीं है।

संबंधित जटिलता वर्ग

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

बाहरी संबंध

• Complexity Zoo: FP