#P-teljes problémaosztály

Kapcsolódó fogalmak: 
#P problémaosztály
Kapcsolódó fogalmak: 
#P-nehéz
Rövid szöveges bemutatás: 
A bonyolultságelmélet (complexity analysis) területe a problémákat elemzi. Létezik a #P osztály probléma osztály, mely olyan problémákat tartalmaz, melyeknek megoldásai egész számok. Ezek a problémák az NP-beli döntési problémáknak megfelelő számlálási problémák. Léteznek azonban olyan számlálási problémák, amik viszont #P-teljesek, amin azt kell érteni, hogy legalább olyan nehéz, mint a #P-beli problémák bármelyike, és így legalább olyan nehéz, mint az NP-beli problémák bármelyike.