Factor de optimización $ le_p $ factorización de decisiones

Question

Factorización de optimización:
Entrada: $ n en mathbb {n} $
Salida: todos los factores primos de $ N $

Decisión de factorización:
Entrada: $ n, k in mathbb {n} $
Salida: Verdadero IFF $ N $ tiene un factor principal de como máximo $ K $

¿Cómo puedo resolver el problema de optimización en el tiempo polinomial si el problema de la decisión se puede solucionar polinomialmente?

Answer 1

Debe obtener un polinomio de algoritmo en $ n $ donde $ n = log n $ es del tamaño de su aporte, es decir, la representación binaria de $ n $ (los algoritmos de factorización ingenuo son $ o (n^2) $ es de Exponencial del curso).

Dado dec(k, x) Resolviendo el problema de factorización de decisión, escribamos un procedimiento para encontrar el divisor principal más pequeño de $ x $ usando una dicotomía para mantener logarítmica el número de pasos.

sp(x):
  min = 2
  max = x - 1
  while (max >= 1 + min):
    k = floor ((min + max) / 2)
    if dec(k, x):
      max = k
    else:
      min = k + 1
  if x % (min + 1) == 0:
    return (min + 1)
  else if x % min == 0:
    return min
  else:
    return 1

El procedimiento anterior llama dec $ O ( log x) $ Times y encuentre el número primo más pequeño que divide $ x $, o 1 Si no existe. Ahora podemos definir fácilmente la siguiente función de factorización:

factor(x):
  p = sp(x)
  if (p == 1):
    print x
  else:
    print p
    factor(x / p)

El factor se llama menos de $ log x $ veces (ya que $ p ≥ 2 $), por lo que el número de llamadas a dec está limitado por $ log^2 x $ veces en valores de menos de $ x $. Si la complejidad de dec es polinomial, digamos limitado por un aumento de $ p (n) $, entonces la complejidad de factor sigue siendo polinomial, limitado por $ n^2p (n) $.

Answer 2

Puede usar la versión de decisión para buscar los factores de $ N $ manipulando $ K $. Dada la entrada a la versión de optimización, puede preguntar si tiene un factor primo menor o igual a $ 2 $, $ 3 $, ..., $ sim sqrt {n} $. Digamos que obtienes tu primera respuesta a $ k_ {1} $, luego porque no dijo que sí antes, $ k_ {1} $ debe ser un factor de $ n $, por lo que podemos anotar esto y comenzar de nuevo desde $ frac {n} {k_ {1}} $.

Idealmente, solo probaríamos los primos hasta $ sim sqrt {n} $, pero no importa si probamos los compuestos también, ya que primero alcanzaremos sus factores primos, por lo que nunca obtendremos Una respuesta de sí para un compuesto.

Luego, para cada búsqueda individual, estamos resolviendo como máximo $ sqrt {n} $ problemas de decisión, y en cada paso (hasta que hayamos terminado) estamos reduciendo $ n $ a menos de $ frac {n} {2 } $, por lo que si podemos resolver el problema de decisión en ptime (digamos $ o (n^{c}) $ por algunas constantes $ c $), podemos hacer todo en algo más o menos como $ o (n^{c +1/2} log n) $.