♯P

في نظرية التعقيد الحسابي ، تُعرف فئة التعقيد #P (تُنطق "شارب بي" أو أحيانًا "نمبر بي" أو "هاش بي") بأنها مجموعة مسائل العد المرتبطة بمسائل القرار في المجموعة NP . وبصورة أدق، تُعرف #P بأنها فئة مسائل الدوال من الشكل "حساب f ( x )"، حيث f هو عدد المسارات المقبولة لآلة تورينج غير حتمية تعمل في زمن متعدد الحدود . وعلى عكس معظم فئات التعقيد المعروفة، فهي ليست فئة مسائل قرار ، بل فئة مسائل دوال . وتُعدّ المسائل الأكثر صعوبة وتمثيلًا لهذه الفئة مسائل #P-كاملة .

يمكن صياغة مشكلة القرار من نوع NP في كثير من الأحيان على النحو التالي: "هل توجد أي حلول تلبي قيودًا معينة؟" على سبيل المثال:

• هل توجد أي مجموعات جزئية من قائمة الأعداد الصحيحة مجموعها يساوي صفرًا؟ ( مسألة مجموع المجموعات الجزئية )
• هل توجد أي دورات هاميلتونية في رسم بياني معين بتكلفة أقل من 100؟ ( مسألة البائع المتجول )
• هل توجد أي قيم للمتغيرات تحقق صيغة CNF (الصيغة الطبيعية الاقترانية) معينة ؟ ( مسألة إرضاء منطقي أو SAT)
• هل لكثير الحدود الحقيقي ذي المتغير الواحد أي جذور موجبة؟ ( إيجاد الجذور )

تُطرح مسائل الدوال من النوع P المقابلة سؤال "كم عدد" بدلاً من سؤال "هل يوجد أي منها؟". على سبيل المثال:

• كم عدد المجموعات الجزئية من قائمة الأعداد الصحيحة التي مجموعها يساوي صفرًا؟
• كم عدد دورات هاميلتون في رسم بياني معين والتي تكلفت أقل من 100؟
• كم عدد تعيينات المتغيرات التي تحقق صيغة CNF معينة؟
• كم عدد الجذور الموجبة لكثير الحدود الحقيقي ذي المتغير الواحد؟

من الواضح أن مسألة #P يجب أن تكون على الأقل بنفس صعوبة مسألة NP المقابلة لها . إذا كان من السهل عدّ الإجابات، فلا بد أن يكون من السهل معرفة ما إذا كانت هناك أي إجابات - يكفي عدّها والتحقق مما إذا كان العدد أكبر من الصفر. بعض هذه المسائل، مثل عدّ الجذور ، سهلة بما يكفي لتكون ضمن فئة FP ، بينما البعض الآخر من فئة #P-complete .

إحدى نتائج نظرية تودا هي أن آلة ذات زمن متعدد الحدود مزودة بـ #P أوراكل ( P ^#P ) تستطيع حل جميع المسائل في PH ، أي التسلسل الهرمي متعدد الحدود بأكمله . في الواقع، لا تحتاج الآلة ذات الزمن متعدد الحدود إلا إلى إجراء استعلام واحد من نوع #P لحل أي مسألة في PH . وهذا دليل على الصعوبة البالغة لحل المسائل الكاملة من نوع #P بدقة.

من المثير للدهشة أن بعض مسائل #P التي يُعتقد أنها صعبة تتطابق مع مسائل P سهلة (مثل مسائل الوقت الخطي) . لمزيد من المعلومات حول هذا الموضوع، انظر #P-complete .

أقرب فئة مسائل قرار إلى #P هي PP ، التي تسأل عما إذا كانت أغلبية (أكثر من النصف) مسارات الحساب مقبولة. تُحدد هذه الفئة البت الأكثر أهمية في إجابة مسألة #P . أما فئة مسائل القرار ⊕P (تُنطق "باريتي-بي") فتسأل عن البت الأقل أهمية في إجابة #P .

يتم تعريف #P رسميًا على النحو التالي:

#P هي مجموعة جميع الدوال${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$بحيث توجد آلة تورينغ غير حتمية ذات زمن متعدد الحدود${\displaystyle M}$بحيث يكون ذلك لجميع${\displaystyle x\in \{0,1\}^{*}}$،${\displaystyle f(x)}$يساوي عدد الفروع المقبولة في${\displaystyle M}$الرسم البياني للحسابات على${\displaystyle x}$[ ^{1 ]​}

يمكن تعريف #P بشكل مكافئ من حيث المُدقِّق. تُصنَّف مسألة القرار ضمن فئة NP إذا وُجدت شهادة قابلة للتحقق في زمن متعدد الحدود لحالة معينة من المسألة - أي أن NP تسأل عما إذا كان هناك برهان انتماء للمدخلات يمكن التحقق من صحته في زمن متعدد الحدود. تسأل الأسئلة في #P عن عدد الشهادات الموجودة لحالة معينة من المسألة والتي يمكن التحقق من صحتها في زمن متعدد الحدود. ^{[ 1 ]} في هذا السياق، تُعرَّف #P ​​على النحو التالي:

#P هي مجموعة الدوال${\displaystyle f:\{0,1\}^{*}\to \mathbb {N} }$بحيث يوجد كثير حدود${\displaystyle p:\mathbb {N} \to \mathbb {N} }$وآلة تورينج حتمية تعمل في وقت متعدد الحدود${\displaystyle V}$، ويسمى المُدقِّق، بحيث يكون لكل${\displaystyle x\in \{0,1\}^{*}}$،${\displaystyle f(x)={\Big |}{\big \{}y\in \{0,1\}^{p(|x|)}:V(x,y)=1{\big \}}{\Big |}}$[ ^{2 ]} (بمعنى آخر ^،${\displaystyle f(x)}$يساوي حجم المجموعة التي تحتوي على جميع الشهادات ذات الحجم متعدد الحدود).

تم تعريف فئة التعقيد #P لأول مرة بواسطة ليزلي فاليانت في مقال عام 1979 حول حساب الثابت لمصفوفة مربعة ، حيث أثبت أن الثابت هو #P-كامل . ^{[ 3 ]}

أثبت لاري ستوكمير أنه لكل مشكلة من مشاكل #P${\displaystyle P}$توجد خوارزمية عشوائية تستخدم وسيطًا لحل مشكلة SAT، والتي عند إعطاء مثال${\displaystyle a}$ل${\displaystyle P}$و${\displaystyle \epsilon >0}$يعود باحتمالية عالية رقمًا${\displaystyle x}$بحيث${\displaystyle (1-\epsilon )P(a)\leq x\leq (1+\epsilon )P(a)}$[ ^{4 ]} زمن تشغيل الخوارزمية متعدد الحدود ^في${\displaystyle a}$و${\displaystyle 1/\epsilon }$تعتمد الخوارزمية على نظرية التجزئة المتبقية .

• الحوسبة الكمومية#العلاقة_بنظرية_الحوسبة_والتعقيد – تقنية أجهزة الكمبيوتر التي تستخدم ميكانيكا الكم 

• حديقة حيوانات التعقيد : الفئة د ب