في نظرية التعقيد P# هو صنف عد عدد مسارات الحساب التي هي «موافقة» في آلة تيورنج غير حتمية، وهذا القسم أو الصنف بخلاف كثير من الاقسام هو قسم دوال وليس مسائل تقرير. هناك علاقة قوية بين هذا القسم وبين القسم NP , حيث أن NP صيغة المسألة فيه «هل يوجد حل الذي يحقق ظروف معينة؟» اما P# فالصيغة هي: «ما هو عدد الحلول التي تحقق الظروف؟» مثال:
المسائل التالية تابعة ل- NP :
هل يوجد قيم للمتغيرات في صيغة على شكل CNF حيث أنَّ الصيغة المُعطاة مكتفية؟
هل يوجد في المُخطط المعطى مسار هاميلتوني؟
هل يوجد مجموعة جزئية لمجموعة اعداد حيث ان مجموع المجموعة الجزئية 0 ؟
اما مسائل P# فهي كالتالي:
ما هو عدد التعويضات في القيم لصيغة بشكل CNF التي هي تجعل الصيغة مكتفية؟
ما هو عدد المسارات الهاملتونية في مخطط معطى؟
ما هو عدد المجموعات الجزئية التي مجموعها 0 ؟
لذا فاننا نعلم ان P# هي على الاقل مثل NP .