एफपी (कॉम्प्लेक्सिटी): Difference between revisions

Latest revision as of 15:10, 30 August 2023

कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत में कॉम्प्लेक्सिटी क्लास एफपी फ़ंक्शन समस्याओं की एक क्लास है जिसे पोलिनोमिअल-टाइम में एक डेटर्मिनिस्टिक ट्यूरिंग मशीन द्वारा हल किया जा सकता है। सामान्यतः यह समस्या क्लास P के एक फ़ंक्शन समस्या का संस्करण है। यह समस्या उस फ़ंक्शन की क्लास है जिसकी यादृच्छिक रूप से प्रारम्भिक कंप्यूटर पर कुशलतापूर्वक गणना की जा सकती है।

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

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

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

एक बाइनरी संबंध

P(x,y)

एफपी में है यदि और केवल यदि कोई डेटर्मिनिस्टिक पोलिनोमिअल-टाइम एल्गोरिदम है जहां

x

दिया गया है और

y

के मान के लिए

P(x,y)

मे स्थित है जो संकेत देता है कि इसमे कोई भी

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.

बाहरी संबंध

Complexity Zoo: FP

[1] Bürgisser, Peter (2000). बीजगणितीय जटिलता सिद्धांत में पूर्णता और कमी. Algorithms and Computation in Mathematics. Vol. 7. Berlin: Springer-Verlag. p. 66. ISBN 3-540-66752-0. Zbl 0948.68082.

[2] 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.

[1]

[2]

@@ Line 1: / Line 1: @@
 {{Short description|Complexity class}}
-[[कम्प्यूटेशनल जटिलता सिद्धांत]] में, [[जटिलता वर्ग]] '''एफपी''' फ़ंक्शन समस्याओं का सेट है जिसे बहुपद समय में एक [[नियतात्मक ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है। यह [[निर्णय समस्या]] वर्ग [[पी (जटिलता)]] का फ़ंक्शन समस्या संस्करण है। सामान्यतः यह उन कार्यों का वर्ग है जिन्हें यादृच्छिककरण के बिना शास्त्रीय कंप्यूटर पर कुशलतापूर्वक गणना की जा सकती है।
+[[कम्प्यूटेशनल जटिलता सिद्धांत|कम्प्यूटेशनल कॉम्प्लेक्सिटी सिद्धांत]] में [[जटिलता वर्ग|कॉम्प्लेक्सिटी क्लास]] '''एफपी''' फ़ंक्शन समस्याओं की एक क्लास है जिसे पोलिनोमिअल-टाइम में एक [[नियतात्मक ट्यूरिंग मशीन|डेटर्मिनिस्टिक ट्यूरिंग मशीन]] द्वारा हल किया जा सकता है। सामान्यतः यह [[निर्णय समस्या|समस्या]] क्लास [[पी (जटिलता)|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>
+एफपी और 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> FP में है यदि और केवल यदि कोई नियतात्मक बहुपद समय एल्गोरिदम है, जो <math>x</math> दिया गया है, या तो कुछ <math>y</math> पाता है जैसे कि <math>P(x,y)</math> रखता है, या संकेत देता है कि ऐसा कोई <math>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) कायम है या नहीं। जिस प्रकार पी और एफपी आपस में घनिष्ठ रूप से संबंधित हैं, उसी प्रकार एनपी एफएनपी से घनिष्ठ रूप से संबंधित है। एफपी = एफएनपी यदि और केवल यदि पी = एनपी।
+* एफएनपी बाइनरी संबंधों का समूह है जिसके लिए एक पोलिनोमिअल-टाइम एल्गोरिथ्म है जो x और y का मान दिए जाने पर जांच करता है कि P(x,y) स्थित है या नहीं स्थित है, जिस प्रकार P और एफपी आपस में घनिष्ठ (क्लोसली) रूप से संबंधित हैं। उसी प्रकार <code>NP</code> भी <code>FNP,</code> <code>FP = FNP</code> और <code>P = NP</code>से अधिक निकटता से संबंधित है।
-* क्योंकि एक मशीन जो लॉगरिदमिक स्पेस का उपयोग करती है, उसमें बहुपद रूप से कई कॉन्फ़िगरेशन होते हैं, एफएल, फ़ंक्शन समस्याओं का सेट जिसे लॉगस्पेस में गणना की जा सकती है, एफपी में निहित है। यह ज्ञात नहीं है कि एफएल = एफपी; यह यह निर्धारित करने की समस्या के अनुरूप है कि निर्णय वर्ग पी और एल बराबर हैं या नहीं।
+* क्योंकि एक मशीन जो लॉगरिदमिक स्पेस का उपयोग करती है और उसमें पोलिनोमिअल रूप से कई कॉन्फ़िगरेशन होते हैं जिसमे एफएल फ़ंक्शन समस्याओं का एक समूह जिसकी लॉगस्पेस में गणना की जा सकती है, एफपी में निहित है। लेकिन यह ज्ञात नहीं है कि <code>'''FL = FP'''</code> यह निर्धारित करने की समस्या के अनुरूप है कि डिसिजन-क्लास P और L बराबर हैं।
 ==संदर्भ==
@@ Line 22: / Line 22: @@
 {{Complexity classes}}
-{{DEFAULTSORT:Fp (Complexity)}}[[Category: जटिलता वर्ग]]
+{{DEFAULTSORT:Fp (Complexity)}}
+[[Category:Collapse templates|Fp (Complexity)]]
+[[Category:Created On 25/07/2023|Fp (Complexity)]]
-[[Category: Machine Translated Page]]
+[[Category:Lua-based templates|Fp (Complexity)]]
-[[Category:Created On 25/07/2023]]
+[[Category:Machine Translated Page|Fp (Complexity)]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Fp (Complexity)]]
+[[Category:Pages with script errors|Fp (Complexity)]]
+[[Category:Short description with empty Wikidata description|Fp (Complexity)]]
+[[Category:Sidebars with styles needing conversion|Fp (Complexity)]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready|Fp (Complexity)]]
+[[Category:Templates generating microformats|Fp (Complexity)]]
+[[Category:Templates that add a tracking category|Fp (Complexity)]]
+[[Category:Templates that are not mobile friendly|Fp (Complexity)]]
+[[Category:Templates that generate short descriptions|Fp (Complexity)]]
+[[Category:Templates using TemplateData|Fp (Complexity)]]
+[[Category:Wikipedia metatemplates|Fp (Complexity)]]
+[[Category:जटिलता वर्ग|Fp (Complexity)]]

v t e Important complexity classes (more)
Considered feasible	DLOGTIME AC⁰ ACC⁰ TC⁰ L SL RL NL NC SC CC P P-complete ZPP RP BPP BQP APX FP
Suspected infeasible	UP NP NP-complete NP-hard co-NP co-NP-complete AM QMA PH ⊕P PP #P #P-complete IP PSPACE PSPACE-complete
Considered infeasible	EXPTIME NEXPTIME EXPSPACE 2-EXPTIME ELEMENTARY PR R RE ALL
Class hierarchies	Polynomial hierarchy Exponential hierarchy Grzegorczyk hierarchy Arithmetical hierarchy Boolean hierarchy
Families of classes	DTIME NTIME DSPACE NSPACE Probabilistically checkable proof Interactive proof system

Anonymous

Search

एफपी (कॉम्प्लेक्सिटी): Difference between revisions

Namespaces

More

Page actions

Latest revision as of 15:10, 30 August 2023

Contents

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

संबंधित कॉम्प्लेक्सिटी क्लास

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

एफपी (कॉम्प्लेक्सिटी): Difference between revisions

Latest revision as of 15:10, 30 August 2023

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

संबंधित कॉम्प्लेक्सिटी क्लास

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories