Démontrer que le problème de l'a de factorisation est dans NP

Question

Essayer de balayer vers le haut sur la théorie de calcul, mais je ne suis pas sûr de solution à ceci:

Prove that the problem of factoring α is in NP.

J'ai le sentiment qu'il peut être lié à la recherche d'un problème NP et trouver une réduction du problème de l'affacturage a.

Answer 1

est simple en fait. P. est dans la multiplication NP est le même que « vérifier toutes les solutions possibles de taille polynomiale en parallèle ». Si alpha est codée comme une longueur n bitstring, les facteurs longueur totale est au plus n + c.

Ce qu'il n'est « NP-complet ». Il n'y a aucun moyen de transformer un problème arbitraire NP dans l'affacturage.

Answer 2

Problème dans P : est un problème, qui est calculable par déterministes Machine de Turing en temps polynomial Problème dans NP : est un problème, STAM est polynomicaly veryfiable par déterministes Machine de Turing.

Dans NP, nous utilisons le non-déterminisme de telle sorte, que nous exigeons qu'une seule branche d'un arbre de calcul pour être accepté (nous essayons « toutes » possibilités au moment « même »). des moyens Polynomicaly veryfiable, que nous avons un certificat (que ce soit c), qui est une solution au mot d'entrée (que ce soit w). Le certificat doit être d'une longueur polynomiale considérant la longueur d'entrée. Notre tâche est seulement de vérifier si un certificat est une solution. Par exemple, dans SAT (problème de satisfyability) un certificat est un assignement correct (qui est deviné non déterministe).

Vous prouvez que votre problème est dans NP: Il existe un DTM qui vérifie une paire (p, c), où w est le numéro d'entrée et c sont les facteurs. Vous devez juste construire un veryfier qui multiplie les facteurs en c et la compare à w.