

Devido a esta equivalência, P/polinomial às vezes é definida como a classe de problemas de decisão que podem ser resolvidos por circuitos booleanos de tamanho polinomiais, ou por um circuito booleano de tamanho polinomial não uniforme.