गणना की समस्या (जटिलता): Difference between revisions
No edit summary |
No edit summary |
||
| (4 intermediate revisions by 3 users not shown) | |||
| Line 3: | Line 3: | ||
:<math>c_R(x)=\vert\{y\mid R(x,y)\}\vert \,</math> | :<math>c_R(x)=\vert\{y\mid R(x,y)\}\vert \,</math> | ||
संगत [[गिनती समारोह|गणना कार्य]] | संगत [[गिनती समारोह|गणना कार्य]] है और | ||
:<math>\#R=\{(x,y)\mid y\leq c_R(x)\}</math> | :<math>\#R=\{(x,y)\mid y\leq c_R(x)\}</math> | ||
| Line 9: | Line 9: | ||
ध्यान दें कि सी<sub>R</sub>एक खोज समस्या है जबकि #R एक निर्णय समस्या है, हालाँकि c<sub>R</sub>'C' [[कुक कमी]] हो सकता है | [[द्विआधारी खोज]] का उपयोग करके #R (उपयुक्त 'C' के लिए) तक कुक-कम किया गया (कारण #R को c का ग्राफ होने के बजाय जिस तरह से परिभाषित किया गया है<sub>R</sub>, इस बाइनरी खोज को संभव बनाना है)। | ध्यान दें कि सी<sub>R</sub>एक खोज समस्या है जबकि #R एक निर्णय समस्या है, हालाँकि c<sub>R</sub>'C' [[कुक कमी]] हो सकता है | [[द्विआधारी खोज]] का उपयोग करके #R (उपयुक्त 'C' के लिए) तक कुक-कम किया गया (कारण #R को c का ग्राफ होने के बजाय जिस तरह से परिभाषित किया गया है<sub>R</sub>, इस बाइनरी खोज को संभव बनाना है)। | ||
ध्यान दें कि cR एक खोज समस्या है जबकि #R एक निर्णय समस्या है, चूँकि ''c<sub>R</sub>'' को '''''C''''' | ध्यान दें कि cR एक खोज समस्या है जबकि #R एक निर्णय समस्या है, चूँकि ''c<sub>R</sub>'' को '''''C''''' कुक-कम करके #R (उपयुक्त '''''C''''' के लिए) बाइनरी खोज का उपयोग किया जा सकता है (कारण #R को जिस तरह से परिभाषित किया गया है, उसके अतिरिक्त ''c<sub>R</sub>'' का ग्राफ, इस बाइनरी खोज को संभव बनाने के लिए है)। | ||
== गणना जटिलता वर्ग == | == गणना जटिलता वर्ग == | ||
यदि NX एक जटिलता वर्ग है जो गैर-नियतात्मक एल्गोरिदम से जुड़ा है गैर-नियतात्मक मशीनें हैं तो ''#X'' = {''#R'' | ''R'' ∈ ''NX''}, NX में प्रत्येक खोज समस्या से संबंधित गणना समस्याओं का समुच्चय है। विशेष रूप से '''#P''' समस्याओं से जुड़ी गणना की समस्याओं का वर्ग है। | यदि NX एक जटिलता वर्ग है जो गैर-नियतात्मक एल्गोरिदम से जुड़ा है गैर-नियतात्मक मशीनें हैं तो ''#X'' = {''#R'' | ''R'' ∈ ''NX''}, NX में प्रत्येक खोज समस्या से संबंधित गणना समस्याओं का समुच्चय है। विशेष रूप से '''#P''' समस्याओं से जुड़ी गणना की समस्याओं का वर्ग है। | ||
जिस तरह एनपी के पास कई-एक कमी के माध्यम से | जिस तरह एनपी के पास कई-एक कमी के माध्यम से '''NP'''-पूर्ण समस्याएं हैं, #P के पास पारिश्रमिक कमी समस्या परिवर्तनों के माध्यम से पूरी समस्याएं हैं जो समाधानों की संख्या को संरक्षित करती हैं। | ||
== यह भी देखें == | == यह भी देखें == | ||
* [[ गप्प ]] | * [[ गप्प ]] | ||
| Line 27: | Line 23: | ||
{{Comp-sci-theory-stub}} | {{Comp-sci-theory-stub}} | ||
[[Category: | [[Category:All stub articles]] | ||
[[Category:Created On 15/05/2023]] | [[Category:Created On 15/05/2023]] | ||
[[Category:Lua-based templates]] | |||
[[Category:Machine Translated Page]] | |||
[[Category:Pages with script errors]] | |||
[[Category:Templates Vigyan Ready]] | |||
[[Category:Templates that add a tracking category]] | |||
[[Category:Templates that generate short descriptions]] | |||
[[Category:Templates using TemplateData]] | |||
[[Category:Theoretical computer science stubs]] | |||
[[Category:कम्प्यूटेशनल समस्याएं]] | |||
Latest revision as of 16:06, 14 June 2023
कम्प्यूटेशनल जटिलता सिद्धांत संगणनीयता सिद्धांत सिद्धांत में गणना की समस्या एक प्रकार की कम्प्यूटेशनल समस्या है। यदि 'R ' एक खोज समस्या है तो
संगत गणना कार्य है और
संबंधित निर्णय समस्या को दर्शाता है। ध्यान दें कि सीRएक खोज समस्या है जबकि #R एक निर्णय समस्या है, हालाँकि cR'C' कुक कमी हो सकता है | द्विआधारी खोज का उपयोग करके #R (उपयुक्त 'C' के लिए) तक कुक-कम किया गया (कारण #R को c का ग्राफ होने के बजाय जिस तरह से परिभाषित किया गया हैR, इस बाइनरी खोज को संभव बनाना है)।
ध्यान दें कि cR एक खोज समस्या है जबकि #R एक निर्णय समस्या है, चूँकि cR को C कुक-कम करके #R (उपयुक्त C के लिए) बाइनरी खोज का उपयोग किया जा सकता है (कारण #R को जिस तरह से परिभाषित किया गया है, उसके अतिरिक्त cR का ग्राफ, इस बाइनरी खोज को संभव बनाने के लिए है)।
गणना जटिलता वर्ग
यदि NX एक जटिलता वर्ग है जो गैर-नियतात्मक एल्गोरिदम से जुड़ा है गैर-नियतात्मक मशीनें हैं तो #X = {#R | R ∈ NX}, NX में प्रत्येक खोज समस्या से संबंधित गणना समस्याओं का समुच्चय है। विशेष रूप से #P समस्याओं से जुड़ी गणना की समस्याओं का वर्ग है।
जिस तरह एनपी के पास कई-एक कमी के माध्यम से NP-पूर्ण समस्याएं हैं, #P के पास पारिश्रमिक कमी समस्या परिवर्तनों के माध्यम से पूरी समस्याएं हैं जो समाधानों की संख्या को संरक्षित करती हैं।
