En la teoría de la complejidad computacional, P/poly es la clase de complejidad de los lenguajes reconocidos por una máquina de Turing de tiempo polinomial con una función de asesoramiento limitada polinomialmente. También se define de manera equivalente como la clase PSIZE de lenguajes que tienen circuitos de tamaño polinómico.[1][2] Esto significa que la máquina que reconoce un idioma puede usar una función de asesoramiento diferente o un circuito diferente dependiendo de la longitud de la entrada y que la función o circuito de asesoramiento variará solo según el tamaño de la entrada.
Por ejemplo, la popular prueba de primalidad Miller-Rabin puede formularse como un algoritmo P/poly: el "consejo" es una lista de candidatos a valores para probar. Es posible calcular previamente una lista de, como máximo, n valores de modo que cada número compuesto de n bits se asegure de tener un testigo a en la lista. Por ejemplo, para determinar correctamente la primalidad de los números de 32 bits, es suficiente probar a = 2, 7 y 61.[3] La existencia de listas cortas de testigos candidatos sigue del hecho de que para cada n compuesto, 3/4s de todos los valores posibles son testigos; un simple argumento de recuento similar a la de la prueba de que BPP en P/poly muestra que existe una lista adecuada de valores a para cada tamaño de entrada, aunque encontrarla puede ser caro.
P/poly, a diferencia de otras clases de tiempo polinomial como P o BPP, generalmente no se considera una clase práctica para la computación. De hecho, contiene todos los lenguajes unarios indecidibles, ninguno de los cuales puede ser resuelto en general por computadoras reales. Por otro lado, si la longitud de entrada está limitada por un número relativamente pequeño y las cadenas de consejos son cortas, puede usarse para modelar algoritmos prácticos con una fase de preprocesamiento costosa separada y una fase de procesamiento rápido, como en el ejemplo anterior.
- ↑ Lutz, Jack H.; Schmidt, William J. (1993), «Circuit size relative to pseudorandom oracles», Theoretical Computer Science 107 (1): 95-119, doi:10.1016/0304-3975(93)90256-S.
- ↑ «Lecture notes on computational complexity by Peter Bro Miltersen». Archivado desde el original el 23 de febrero de 2012. Consultado el 25 de diciembre de 2009.
- ↑ Finding primes & proving primality