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

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

$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, इस बाइनरी खोज को संभव बनाना है)।

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

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

यह भी देखें

• गप्प

बाहरी संबंध

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