Algunos ejemplos de #P-completo incluyen: Se piensa que no hay algoritmos en tiempo polinómico para resolver problemas #P-completos.
Inclusive, no se conocen algoritmos deterministas que puedan dar una solución aproximada de calidad razonable.
Sin embargo, existen algoritmos probabilísticos que dan una buena aproximación a algunos problemas #P-completos con una muy buena probabilidad.
Resulta sorprendente que algunos problemas #P-completos corresponden a problemas en P. El segundo de los ejemplos dados anteriormente está en esta categoría.
Específicamente, para un grafo con V vértices y E aristas, la pregunta se puede responder en tiempo O(VE).