Optimisation affacturage $ \ le_p décision-affacturage $

Question

affacturage d'optimisation:
Entrée: $ N \ in \ mathbb {N} $
Sortie: Tous les principaux facteurs de $ N $

affacturage de la décision:
Entrée: $ N, k \ in \ mathbb {N} $
Sortie: True ssi $ N $ a un facteur premier d'au plus k $ $

Comment puis-je résoudre le problème d'optimisation en temps polynomial si le problème de décision est polynomiale résoluble?

Answer 1

Vous devez obtenir un polynôme algorithme $ n $ n $ = \ log N $ est la taille de votre entrée, à savoir la représentation binaire de $ N $ (algorithmes de factorisation naïfs sont O $ (N ^ 2) $ qui est bien sûr exponentielle).

dec(k, x) Compte tenu de la résolution du problème d'affacturage de décision, Écrivons une procédure pour trouver le plus petit diviseur premier de $ x $ en utilisant une dichotomie pour maintenir logarithmique le nombre d'étapes.

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

La procédure ci-dessus appels dec $ O (\ log x) $ fois et trouver le plus petit nombre premier qui divise $ x $, ou 1 si elle n'existe pas. Maintenant, nous pouvons facilement définir la fonction d'affacturage suivante:

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

facteur est appelé à moins de $ \ log x fois $ (depuis $ p = 2 $) de sorte que le nombre d'appels à dec est limitée par $ \ log ^ 2 x fois $ sur des valeurs inférieures à $ x $. Si la complexité de dec est polynomiale, disons bornées par une augmentation de $ P (n) $, la complexité de factor est encore polynomiale, borné par n $ ^ 2P (n) $.

Answer 2

Vous pouvez utiliser la version de la décision de rechercher les facteurs de $ N $ en manipulant $ k $. Compte tenu de l'entrée à la version d'optimisation, vous pouvez demander si elle a un facteur premier inférieur ou égal à 2 $, 3 $ $, ..., $ \ sim \ sqrt {N} $. Dites que vous obtenez votre première réponse à $ K_ {1} $, alors parce qu'il n'a pas dit oui avant, $ K_ {1} $ doit être un facteur de $ N $, afin que nous puissions noter cette baisse, et recommencer à partir $ \ frac {N} {{1} K_} $.

Idéalement nous aimerions tester que les nombres premiers jusqu'à $ \ sim \ sqrt {N} $, mais il n'a pas d'importance si nous testons les matériaux composites et, comme nous allons frapper leurs facteurs premiers d'abord, donc nous ll jamais une réponse Oui pour un composite.

Ensuite, pour chaque recherche individuelle, nous résolvons au plus $ \ sqrt {N} $ Problèmes de décision, et à chaque étape (jusqu'à ce que nous aurons terminé) nous réduisons N $ $ à moins de $ \ frac {N } {2} $, donc si nous pouvons résoudre le problème de la décision PTIME (disons O $ (n ^ {c}) $ pour quelque $ constant c $), nous pouvons faire tout cela quelque chose à peu près comme O $ (n ^ {c + 1/2} \ log n) $.