PP (clase de complejidad)

En teoría de la complejidad computacional PP, que quiere decir tiempo polinomial probabilístico, es una clase de problema de decisión resoluble por una máquina de Turing probabilística ( diferente de la máquina de Turing general o determinista, en que las transiciones entre estados tienen la misma probabilidad de ocurrencia) con un error de probabilidad de menos de 1/2 para todas las instancias.​

Ejemplos

Un ejemplo de algoritmo con esta clase de complejidad es el Test de Solovay-Strassen que permite determinar si un número es primo o compuesto. El algoritmo tiene tiempo polinomial sobre la magnitud de la entrada. El algoritmo se basa en que si el número m de entrada es primo, entonces la salida es primo, pero si m es compuesto, la salida puede ser primo con probabilidad a lo más un medio. El algoritmo puede ser repetido cualquier número de veces con resultados independientes. Así, si la respueta alguna vez es compuesto, sabemos que es compuesto, mientras que si la respuesta es siempre primo, después de un número i de veces, entonces podemos decir sin apenas riesgo de equivocarnos que es primo, dado que fijado un compuesto cualquiera m, la probabilidad de que se diera ese resultado es menor que $2^{-i}$​

Otro ejemplo es el algoritmo Berlekamp, para factorizar un polinomio f sobre el cuerpo de los campos de Galois.​

Referencias

• Datos: Q1563053