Tengo problemas para comprender los problemas PRIME, COMPUESTO, FACTOR y cómo están relacionados en términos de complejidad. Entiendo que PRIME ha demostrado estar en mediante la prueba de primalidad AKS, y creo que esto también funciona para COMPOSITE.
En cuanto a FACTOR,
por lo que he leído parece que está en . Veo que está en N P ya que un certificado consistiría en un divisor principal de m menor que r . Pero, ¿qué tipo de certificado puede establecer que no existe tal divisor principal (en tiempo polinómico)?
complexity-theory
factoring
Fequish
fuente
fuente
Respuestas:
fuente
Para agregar a la respuesta de Yuval: La prueba de primalidad AKS se descubrió en 2002. Antes de eso, no teníamos un algoritmo de tiempo polinómico para verificar si un número es primo. Sin embargo, Pratt descubrió en 1975 lo que ahora se conoce como certificados Pratt de primalidad y demostró que Primes está en NP. Podemos incluir estos certificados de primitividad de Pratt para los factores en nuestro certificado para mostrar que FACTOR está en coNP en lugar de usar el algoritmo AKS para verificar si los factores son primos directamente.
fuente