गणना की समस्या (जटिलता)

कम्प्यूटेशनल जटिलता सिद्धांत संगणनीयता सिद्धांत सिद्धांत में गणना की समस्या एक प्रकार की कम्प्यूटेशनल समस्या है। यदि 'R ' एक खोज समस्या है तो

$c_{R}(x)=\vert \{y\mid R(x,y)\}\vert \,$

संगत गणना कार्य है और

$\#R=\{(x,y)\mid y\leq c_{R}(x)\}$

संबंधित निर्णय समस्या को दर्शाता है। ध्यान दें कि सी_Rएक खोज समस्या है जबकि #R एक निर्णय समस्या है, हालाँकि c_R'C' कुक कमी हो सकता है | द्विआधारी खोज का उपयोग करके #R (उपयुक्त 'C' के लिए) तक कुक-कम किया गया (कारण #R को c का ग्राफ होने के बजाय जिस तरह से परिभाषित किया गया है_R, इस बाइनरी खोज को संभव बनाना है)।

ध्यान दें कि cR एक खोज समस्या है जबकि #R एक निर्णय समस्या है, चूँकि c_R को C कुक-कम करके #R (उपयुक्त C के लिए) बाइनरी खोज का उपयोग किया जा सकता है (कारण #R को जिस तरह से परिभाषित किया गया है, उसके अतिरिक्त c_R का ग्राफ, इस बाइनरी खोज को संभव बनाने के लिए है)।

गणना जटिलता वर्ग

यदि NX एक जटिलता वर्ग है जो गैर-नियतात्मक एल्गोरिदम से जुड़ा है गैर-नियतात्मक मशीनें हैं तो #X = {#R | R ∈ NX}, NX में प्रत्येक खोज समस्या से संबंधित गणना समस्याओं का समुच्चय है। विशेष रूप से #P समस्याओं से जुड़ी गणना की समस्याओं का वर्ग है।

जिस तरह एनपी के पास कई-एक कमी के माध्यम से NP-पूर्ण समस्याएं हैं, #P के पास पारिश्रमिक कमी समस्या परिवर्तनों के माध्यम से पूरी समस्याएं हैं जो समाधानों की संख्या को संरक्षित करती हैं।

यह भी देखें

• गप्प

बाहरी संबंध

• "counting problem". PlanetMath.
• "counting complexity class". PlanetMath.