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]
Otro ejemplo es el algoritmo Berlekamp, para factorizar un polinomio f sobre el cuerpo de los campos de Galois.[2]
Referencias
Complexity Theory and Cryptology: An Introduction to Cryptocomplexity. pp 270. Jörg Rothe. Springer 2005
↑ Complejidad Algorítmica. Juan Luis Castro Peña. 1996 Depto. Ciencias de la Computación e Inteligencia Artificial. Universidad de Granada
Datos:Q1563053
Septiembre 22, 2021
clase, complejidad, teoría, complejidad, computacional, quiere, decir, tiempo, polinomial, probabilístico, clase, problema, decisión, resoluble, máquina, turing, probabilística, diferente, máquina, turing, general, determinista, transiciones, entre, estados, t. En teoria de la complejidad computacional PP que quiere decir tiempo polinomial probabilistico es una clase de problema de decision resoluble por una maquina de Turing probabilistica diferente de la maquina 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 1 Ejemplos EditarUn ejemplo de algoritmo con esta clase de complejidad es el Test de Solovay Strassen que permite determinar si un numero es primo o compuesto El algoritmo tiene tiempo polinomial sobre la magnitud de la entrada El algoritmo se basa en que si el numero m de entrada es primo entonces la salida es primo pero si m es compuesto la salida puede ser primo con probabilidad a lo mas un medio El algoritmo puede ser repetido cualquier numero de veces con resultados independientes Asi si la respueta alguna vez es compuesto sabemos que es compuesto mientras que si la respuesta es siempre primo despues de un numero 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 displaystyle 2 i 2 Otro ejemplo es el algoritmo Berlekamp para factorizar un polinomio f sobre el cuerpo de los campos de Galois 2 Referencias Editar Complexity Theory and Cryptology An Introduction to Cryptocomplexity pp 270 Jorg Rothe Springer 2005 a b Complejidad Algoritmica Juan Luis Castro Pena 1996 Depto Ciencias de la Computacion e Inteligencia Artificial Universidad de Granada Datos Q1563053Obtenido de https es wikipedia org w index php title PP clase de complejidad amp oldid 119491810, wikipedia, wiki, leyendo, leer, libro, biblioteca,
