Un problema de decisión está en la clase de complejidad P/f(n) si hay un tiempo polinómico en la máquina de Turing M con la siguiente propiedad: para cualquier n, hay una cadena de aviso A de longitud f(n) tal que, para cualquier entrada x de longitud n, la máquina M decide correctamente el problema en la entrada x, dados x y A.
Simular una máquina de Turing con consejos no es más complicado que simular una máquina ordinaria, ya que la cadena de consejos se puede incorporar al circuito.
P/poly contiene P y BPP (teorema de Adleman).
Si se nos permite un consejo de longitud 2n, podemos usarlo para codificar si cada entrada de longitud n está contenida en el lenguaje.
Por lo tanto, cualquier función booleana es computable con un consejo de longitud 2n y un consejo de longitud más que exponencial no es significativo.