P/poly

Carta Común · N.º 445503

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.​​ 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…

Leer en Wikipedia