एफपी (कॉम्प्लेक्सिटी): Difference between revisions
From Vigyanwiki
(Created page with "{{Short description|Complexity class}} कम्प्यूटेशनल जटिलता सिद्धांत में, जटिलता वर्ग ए...") |
No edit summary |
||
| Line 1: | Line 1: | ||
{{Short description|Complexity class}} | {{Short description|Complexity class}} | ||
[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, [[जटिलता वर्ग]] एफपी फ़ंक्शन समस्याओं का सेट है जिसे बहुपद समय में एक [[नियतात्मक ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है। यह [[निर्णय समस्या]] वर्ग [[पी (जटिलता)]] का फ़ंक्शन समस्या संस्करण है। | [[कम्प्यूटेशनल जटिलता सिद्धांत]] में, [[जटिलता वर्ग]] '''एफपी''' फ़ंक्शन समस्याओं का सेट है जिसे बहुपद समय में एक [[नियतात्मक ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है। यह [[निर्णय समस्या]] वर्ग [[पी (जटिलता)]] का फ़ंक्शन समस्या संस्करण है। सामान्यतः यह उन कार्यों का वर्ग है जिन्हें यादृच्छिककरण के बिना शास्त्रीय कंप्यूटर पर कुशलतापूर्वक गणना की जा सकती है। | ||
एफपी और पी के बीच अंतर यह है कि पी में समस्याओं का उत्तर एक-बिट, हां/नहीं में होता है, जबकि एफपी में समस्याओं का कोई भी आउटपुट हो सकता है जिसकी गणना बहुपद समय में की जा सकती है। उदाहरण के लिए, दो संख्याओं को जोड़ना एक एफपी समस्या है, जबकि यह निर्धारित करना कि उनका योग विषम है या नहीं, पी में है।<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> FP में है यदि और केवल यदि कोई नियतात्मक बहुपद समय एल्गोरिदम है, जो <math>x</math> दिया गया है, या तो कुछ <math>y</math> पाता है जैसे कि <math>P(x,y)</math> रखता है, या संकेत देता है कि ऐसा कोई <math>y</math> मौजूद नहीं है। | ||
==संबंधित जटिलता वर्ग== | ==संबंधित जटिलता वर्ग== | ||
* | * एफएनपी द्विआधारी संबंधों का सेट है जिसके लिए एक बहुपद समय एल्गोरिथ्म है, जो x और y दिए जाने पर जांच करता है कि P(x,y) कायम है या नहीं। जिस प्रकार पी और एफपी आपस में घनिष्ठ रूप से संबंधित हैं, उसी प्रकार एनपी एफएनपी से घनिष्ठ रूप से संबंधित है। एफपी = एफएनपी यदि और केवल यदि पी = एनपी। | ||
* क्योंकि एक मशीन जो लॉगरिदमिक स्पेस का उपयोग करती है, उसमें बहुपद रूप से कई कॉन्फ़िगरेशन | * क्योंकि एक मशीन जो लॉगरिदमिक स्पेस का उपयोग करती है, उसमें बहुपद रूप से कई कॉन्फ़िगरेशन होते हैं, एफएल, फ़ंक्शन समस्याओं का सेट जिसे लॉगस्पेस में गणना की जा सकती है, एफपी में निहित है। यह ज्ञात नहीं है कि एफएल = एफपी; यह यह निर्धारित करने की समस्या के अनुरूप है कि निर्णय वर्ग पी और एल बराबर हैं या नहीं। | ||
==संदर्भ== | ==संदर्भ== | ||
Revision as of 16:05, 6 August 2023
कम्प्यूटेशनल जटिलता सिद्धांत में, जटिलता वर्ग एफपी फ़ंक्शन समस्याओं का सेट है जिसे बहुपद समय में एक नियतात्मक ट्यूरिंग मशीन द्वारा हल किया जा सकता है। यह निर्णय समस्या वर्ग पी (जटिलता) का फ़ंक्शन समस्या संस्करण है। सामान्यतः यह उन कार्यों का वर्ग है जिन्हें यादृच्छिककरण के बिना शास्त्रीय कंप्यूटर पर कुशलतापूर्वक गणना की जा सकती है।
एफपी और पी के बीच अंतर यह है कि पी में समस्याओं का उत्तर एक-बिट, हां/नहीं में होता है, जबकि एफपी में समस्याओं का कोई भी आउटपुट हो सकता है जिसकी गणना बहुपद समय में की जा सकती है। उदाहरण के लिए, दो संख्याओं को जोड़ना एक एफपी समस्या है, जबकि यह निर्धारित करना कि उनका योग विषम है या नहीं, पी में है।[1] बहुपद-समय फ़ंक्शन समस्याएं बहुपद-समय कटौती को परिभाषित करने में मौलिक हैं, जिनका उपयोग एनपी-पूर्ण समस्याओं के वर्ग को परिभाषित करने के लिए किया जाता है।[2]
औपचारिक परिभाषा
एफपी को औपचारिक रूप से इस प्रकार परिभाषित किया गया है:
- एक द्विआधारी संबंध FP में है यदि और केवल यदि कोई नियतात्मक बहुपद समय एल्गोरिदम है, जो दिया गया है, या तो कुछ पाता है जैसे कि रखता है, या संकेत देता है कि ऐसा कोई मौजूद नहीं है।
संबंधित जटिलता वर्ग
- एफएनपी द्विआधारी संबंधों का सेट है जिसके लिए एक बहुपद समय एल्गोरिथ्म है, जो 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.
