#P-nehéz

Kapcsolódó fogalmak: 
#P problémaosztály
Kapcsolódó fogalmak: 
#P-teljes problémaosztály
Rövid szöveges bemutatás: 
A bonyolultságelmélet (complexity analysis) területe a problémákat elemzi. A problémák bonyolultságának fő osztályai a P (polinom időben megoldható) és az NP (nemdeterminisztikus polinom idejű problémák). Léteznek azonban NP-beli döntési problémáknak megfelelő számlálási problémák, melyek megoldásai egész számok. Ezeket a problémákat tartalmazza a #P osztály, mely feladatok #P-nehezek („számosság-P-nehéz”), azaz szigorúan nehezebbek, mint az NP-teljes problémák.