กลุ่มปัญหาการนับที่สำคัญที่สุดคือกลุ่ม #P ซึ่งเป็นปัญหาการนับที่สอดคล้องกับกลุ่มปัญหาการตัดสินใจประเภท NP ปัญหา NP คือปัญหาการตัดสินใจที่ถามว่า "เมื่อกำหนดตัวอย่างปัญหามาให้ จะมีวิธีแก้ปัญหาอย่างน้อยหนึ่งวิธีหรือไม่" และยิ่งไปกว่านั้น ปัญหา NP ยังมาพร้อมกับเครื่องจักรทัวริงสำหรับตรวจสอบวิธีแก้ปัญหาที่ทำงานในเวลาพหุนาม

ปัญหา #P ที่เกี่ยวข้องจึงถามว่า: "เมื่อกำหนดตัวอย่างปัญหามาให้ จะมีคำตอบกี่คำตอบ?" กล่าวโดยย่อคือ #P นับจำนวนเส้นทางที่ยอมรับได้ของเครื่องจักรทัวริงแบบไม่กำหนดที่ทำงานในเวลาพหุนาม

เช่นเดียวกับที่NPมีปัญหาNP-complete ผ่าน การลดแบบ many-one ปัญหา #P ก็มีปัญหา #P-complete ผ่านการลดแบบ parsimonious ในเวลาพหุนามเช่นกัน เมื่อกำหนดปัญหาการค้นหาสองปัญหา${\displaystyle A,B}$การลดรูปอย่างประหยัดด้วยเวลาพหุนามจาก${\displaystyle A}$ถึง${\displaystyle B}$เป็นฟังก์ชัน${\displaystyle f}$โดยที่

• ${\displaystyle f}$สามารถคำนวณได้ในเวลาพหุนาม
• สำหรับปัญหาใดๆ ก็ตาม${\displaystyle x_{A}}$ของ${\displaystyle A}$มันเชื่อมโยงกับตัวอย่างปัญหา${\displaystyle f(x_{A})}$ของ${\displaystyle B}$โดยที่${\displaystyle x_{A}}$และ${\displaystyle f(x_{A})}$มีจำนวนวิธีแก้ปัญหาเท่ากัน^{[ 2 ]}

การลดรูปนี้เป็นแบบสะท้อนและถ่ายทอดได้ ปัญหาบางอย่างเป็น ♯P-complete ภายใต้การลดรูปการนับแบบประหยัดในเวลาพหุนาม เช่น ปัญหา #3SAT เพื่อแสดงให้เห็นสิ่งนี้ เพียงแค่ใช้การพิสูจน์มาตรฐานที่ว่าปัญหา 3SAT เป็น NP-complete และสังเกตว่าการลดรูปที่ใช้ในการพิสูจน์นั้นประหยัดอยู่แล้ว ตัวอย่างเพิ่มเติมมีอยู่ในหน้าการลดรูปแบบประหยัด

การลดรูปนับหลายหนึ่งในเวลาพหุนามเป็นอีกรูปแบบหนึ่งของการลดรูปที่ยืดหยุ่นกว่า โดยกำหนดปัญหาการค้นหาสองปัญหา${\displaystyle A,B}$การลดรูปหลายหนึ่งในเวลาพหุนามจาก${\displaystyle A}$ถึง${\displaystyle B}$ประกอบด้วยสองฟังก์ชัน${\displaystyle f,g}$โดยที่

• ${\displaystyle f,g}$สามารถคำนวณได้ในเวลาพหุนาม
• สำหรับปัญหาใดๆ ก็ตาม${\displaystyle x_{A}}$ของ${\displaystyle A}$,${\displaystyle f}$แมปไปยังอินสแตนซ์ปัญหา${\displaystyle f(x_{A})}$ของ${\displaystyle B}$โดยที่จำนวนคำตอบของ${\displaystyle x_{A}}$คำนวณโดยการแมปจำนวนคำตอบไปยัง${\displaystyle f(x_{A})}$โดยใช้${\displaystyle g}$:$${\displaystyle c_{A}(x_{A})=g(c_{B}(f(x_{A})))}$$

ปัญหาการนับที่คล้ายคลึงกันของปัญหา NP-complete ตามธรรมชาติหลายปัญหาเป็นปัญหา #P-complete แต่ในทางกลับกันนั้นไม่เป็นเช่นนั้น: ปัญหาการตัดสินใจบางอย่างสอดคล้องกับปัญหาการนับ #P-complete แม้ว่าปัญหาเหล่านั้นจะอยู่ใน P หรือแม้กระทั่งสามารถตัดสินใจได้อย่างง่ายดายก็ตาม

ตัวอย่างเช่นปัญหาการนับ 01-ถาวรนั้น ♯P-สมบูรณ์ภายใต้การลดการนับหลายหนึ่งในเวลาพหุนาม ปัญหานี้เทียบเท่ากับการนับการจับคู่ที่สมบูรณ์แบบในกราฟสองส่วนการตัดสินใจว่ามีการจับคู่ที่สมบูรณ์แบบในกราฟสองส่วนหรือไม่นั้นใช้เวลาพหุนามโดย อัลกอริ ทึมHopcroft–Karp ^{[ 3 ]}

ยังมีปัญหาอื่นๆ อีกที่ใช้เวลาในการตัดสินใจแบบพหุนาม แต่การนับนั้นถือว่า #P-complete: ^{[ 4 ]}

• ต้นไม้แผ่ขยายของกราฟ
• วงจรออยเลอร์ของกราฟทิศทาง
• การจับคู่ที่สมบูรณ์แบบของกราฟระนาบ

มีปัญหาบางอย่างที่ตัดสินใจได้ง่าย แต่การนับปัญหานั้นต้องใช้ความสมบูรณ์แบบ #P:

• การกำหนดค่าที่สอดคล้องกับสูตรบูลีนแบบโมโนโทน (สูตรที่ไม่มีสัญลักษณ์ปฏิเสธ) จะมีค่าที่สอดคล้องอย่างน้อยหนึ่งค่าเสมอ โดยการตั้งค่าตัวแปรทั้งหมดเป็น True
• จุดที่ไม่ คลิก ในกราฟขนาด${\displaystyle \lceil n/2\rceil }$, ที่ไหน${\displaystyle n}$คือจำนวนจุดยอด ถ้ากราฟทั้งหมดมีจุดยอดคู่ใดคู่หนึ่งที่ไม่ได้เชื่อมต่อกันด้วยเส้นขอบ ก็จะมีจุดยอดที่ไม่เป็นกลุ่ม (non-clique) อยู่
• ป่าที่แผ่ขยายของกราฟระนาบสองส่วน จะมีอยู่อย่างน้อยหนึ่งแห่งเสมอ
• ส่วนขยายเชิงเส้นของลำดับบางส่วนบนเซตจำกัด จะมีอย่างน้อยหนึ่งส่วนขยายเสมอ

มีโจทย์ปัญหาการนับบางข้อที่ทราบกันว่ายากระดับ #P แต่ก็อาจจะยากเกินระดับ #P ได้เช่นกัน:

• กำหนดกราฟสองกราฟ นับจำนวนกราฟไอโซมอร์ฟิซึมระหว่างกราฟทั้งสอง เป็นที่ทราบกันว่าสามารถคำนวณได้ในเวลาพหุนามเมื่อกำหนดออราเคิล NP ^{[ 5 ]}
• กำหนดกราฟมาให้ จงนับจำนวนกราฟย่อยที่เป็นกราฟแฮมิลโทเนียน

Mod P ถามว่า: "เมื่อกำหนดตัวอย่างปัญหามาให้ จำนวนคำตอบหารด้วยk ลงตัวหรือ ไม่?" สำหรับทุก k≥2, Mod P จะประกอบด้วยปัญหาไอโซมอร์ฟิซึมของกราฟนอกจากนี้ ปัญหาไอโซมอร์ฟิซึมของกราฟยังมีค่าต่ำใน Mod P เมื่อkเป็นจำนวนเฉพาะ เซตของภาษาที่มีค่าต่ำใน Mod P ก็คือ Mod P นั่นเอง

⊕P ถูกกำหนดให้เป็น Mod P โดยถามว่า "เมื่อกำหนดตัวอย่างปัญหามาให้ จำนวนคำตอบเป็นเลขคู่หรือเลขคี่?" ซึ่งตัวมันเอง ก็ มีค่าต่ำ :${\displaystyle \oplus {\mathsf {P}}^{\oplus {\mathsf {P}}}=\oplus {\mathsf {P}}}$.

PPหรือ PPT คือกลุ่มของปัญหาการตัดสินใจที่สามารถแก้ไขได้ด้วยเครื่องจักรทัวริงเชิงความน่าจะเป็นในเวลาพหุนาม โดยมีความน่าจะเป็นของข้อผิดพลาดน้อยกว่า 1/2 สำหรับทุกกรณี ซึ่งสามารถนิยามได้อีกอย่างว่า: "เมื่อกำหนดตัวอย่างปัญหาเชิงบวก และเครื่องจักรทัวริงแบบไม่กำหนดในเวลาพหุนาม คำตอบที่เป็นไปได้มากกว่าครึ่งหนึ่งนั้นถูกต้องหรือไม่?"

โปรดทราบว่า เพื่อให้คำถามมีความหมาย เราต้องกำหนดเซตของ "คำตอบที่เป็นไปได้" ก่อน ในกรณีส่วนใหญ่ของปัญหา NP เซตของ "คำตอบที่เป็นไปได้" นั้นชัดเจน ตัวอย่างเช่น สำหรับปัญหา SATตัวอย่างของปัญหาคือสูตรบูลีน${\displaystyle \phi }$และเซตของคำตอบที่เป็นไปได้คือเซตของการกำหนดค่าบูลีน${\displaystyle V\to \{0,1\}}$, ที่ไหน${\displaystyle V}$คือชุดของตัวแปรใน${\displaystyle \phi }$.

คลาสFewP ("NP ที่มีพยานน้อย") ถูกนิยามว่าเป็นคลาสเฉพาะของปัญหาการตัดสินใจแบบ NP โดยเฉพาะอย่างยิ่ง ปัญหาการตัดสินใจจะเป็น FewP ก็ต่อเมื่อมีเครื่องจักรทัวริงแบบไม่กำหนดที่สามารถแก้ปัญหานั้นได้ในเวลาพหุนาม และสำหรับตัวอย่างปัญหาใดๆ ก็ตาม${\displaystyle x}$มีอยู่มากที่สุด${\displaystyle {\mathsf {poly}}(|x|)}$ยอมรับเส้นทางสำหรับเครื่องจักร

โดยสัญชาตญาณแล้ว นี่คือกลุ่มของปัญหาการตัดสินใจที่หากเป็นเท็จ จะไม่มีพยาน และหากเป็นจริง จะมีพยานเพียงจำนวนพหุนาม (จึงเรียกว่า "น้อย") แตกต่างจากกลุ่มปัญหา NP เต็มรูปแบบ ซึ่งหากเป็นจริง อาจมีพยานจำนวนมหาศาล กลุ่มที่เข้มงวดกว่านั้นคือ UP ("NP ที่ไม่กำกวม") ซึ่งเป็นกลุ่มของปัญหาการตัดสินใจที่มีพยานอย่างมากที่สุด 1 คน

ชั้นเรียนมีขนาดเล็กมาก เนื่องจาก FewP ⊆ ⊕P ซึ่งหมายความว่า FewP มีค่าต่ำสำหรับ ⊕P นอกจากนี้ FewP ยังมีค่าต่ำสำหรับ PP ด้วย^{[ 6 ] [ 7 ]}

GapPได้มาจากการปิด #P ภายใต้การลบ กล่าวคือ ถามว่า "เมื่อกำหนดตัวอย่างปัญหามาให้ จำนวนคำตอบลบด้วยจำนวนคำตอบที่ไม่ใช่คำตอบคือเท่าใด" โดยที่คำตอบที่ไม่ใช่คำตอบจะต้องมาจากเซตของคำตอบที่เป็นไปได้ ซึ่งกำหนดไว้ในลักษณะเดียวกับในคลาส PP ผลต่างนี้เรียกว่า "ช่องว่าง" (gap)

C P ถามว่า: "เมื่อกำหนดตัวอย่างปัญหาแล้ว ช่องว่างเป็นศูนย์หรือไม่?" ได้รับการพิสูจน์แล้วว่าเป็นส่วนเติมเต็มของเวลาพหุนามควอนตัมแบบไม่กำหนด (coNQPT) ^{[ 8 ]}

# L, C L, Mod L, ⊕L, เป็นต้น เป็นอนาล็อกของlogspaceของ #P, C P, Mod P, ⊕P, เป็นต้นฟังก์ชันดีเทอร์มิแนนต์ของเมทริกซ์เป็น #L-สมบูรณ์^{[ 9 ]}

สำหรับเครื่อง Oracleที่ใช้ #P-oracles นั้น เรามี$${\displaystyle {\mathsf {PP}}^{\mathsf {PH}}\subset {\mathsf {P}}^{\#{\mathsf {P}}}={\mathsf {P}}^{\mathsf {PP}}\subset {\mathsf {PSPACE}}}$$อีกด้วย,${\displaystyle {\mathsf {PH}}\subset {\mathsf {P}}^{\#{\mathsf {P}}[1]}}$กล่าวคือ ปัญหาใดๆ ใน คลาส ลำดับชั้นพหุนามสามารถแก้ไขได้ในเวลาพหุนาม หากเราอนุญาตให้เรียกใช้ #P-oracle เพียงครั้งเดียว^{[ 10 ]}นี่เรียกว่าทฤษฎีบทของโทดะและทำให้เซอิโนะสุเกะ โทดะ ได้รับ รางวัลเกอเดลในปี 1998 ^{[ 11 ]}

มีหลักฐานที่แน่ชัดว่าคลาสการนับที่เกิดขึ้นตามธรรมชาติหลายคลาส (PP, C P, Mod P เป็นต้น) นั้นยากกว่า PH อย่างแน่นอน เนื่องจากมีการพิสูจน์แล้วว่าหากคลาสเหล่านั้นไม่ยากกว่า PH อย่างแน่นอน PH ก็จะพังทลายลง ซึ่งถือกันโดยทั่วไปว่าไม่น่าจะเกิดขึ้นได้^{[ 12 ]}