Counting problem (complexity)
کمپیوٹیشنل پیچیدگی تھیوری اور کمپیوٹیبلٹی تھیوری میں، گنتی کا مسئلہ ایک قسم کا کمپیوٹیشنل مسئلہ ہے۔ اگر R تلاش کا مسئلہ ہے تو متعلقہ گنتی فنکشن ہے اور متعلقہ فیصلے کے مسئلے کی نشاندہی کرتا ہے۔ نوٹ کریں کہ سی آر ایک تلاش کا مسئلہ ہے جبکہ #R ایک فیصلہ کا مسئلہ ہے، تاہم سی آر کو بائنری سرچ کا استعمال کرتے ہوئے سی کک کو کم کر کے #R (مناسب سی کے لیے) کیا جا سکتا ہے (وجہ #R کو اس طرح بیان کیا گیا ہے، بجائے اس کے کہ سی آر کا گراف ہو، اس بائنری سرچ کو ممکن بنانا ہے)۔ گنتی کی پیچیدگی کی کلاس اگر این ایکس ایک پیچیدگی کی کلاس ہے جو غیر متعین مشینوں سے وابستہ ہے تو #X = {#R | R bul NX} این ایکس میں ہر تلاش کے مسئلے سے وابستہ گنتی کے مسائل کا مجموعہ ہے۔ خاص طور پر، #P NP تلاش کے مسائل سے وابستہ گنتی کے مسائل کی کلاس ہے۔ جس طرح این پی میں کئی ایک کمی کے ذریعے این پی مکمل مسائل ہوتے ہیں، اسی طرح #P میں غیر معمولی کمی، مسئلہ کی تبدیلیوں کے ذریعے مکمل مسائل ہوتے ہیں جو حل کی تعداد کو محفوظ رکھتے ہیں۔ جی اے پی پی بیرونی روابط کمپیوٹیشنل مسائل بھی دیکھیں۔