Beweisen Sie, dass das Problem des Factorings a in NP ist

Question

Der Versuch, auf Berechnung Theorie auffrischen, aber ich bin nicht sicher, ob der Lösung dieses Problems:

Prove that the problem of factoring α is in NP.

Ich habe das Gefühl, es zu finden, ein NP-Problem und die Suche nach einer Reduzierung des Problem des Factorings a in Beziehung gesetzt werden kann.

Answer 1

Dies ist eigentlich einfach. Die Multiplikation ist in P. NP ist das gleiche wie „alle möglichen Polynom Größe Lösungen parallel Überprüfung“. Wenn alpha als längencodierten n Bitstring, die Faktoren Gesamtlänge beträgt höchstens n + c.

Was es nicht ist "NP-complete". Es gibt keine Möglichkeit, ein beliebiges NP-Problem in Factoring zu machen.

Answer 2

Problem in P : ist ein Problem, das durch deterministische Turing-Maschine in Polynomialzeit berechenbar ist Problem in NP : ein Problem ist, ist thas polynomicaly veryfiable durch deterministische Turing-Maschine.

In NP verwenden wir nicht-Determinismus in einer solchen Art und Weise, dass wir nur einen Zweig eines Berechnungsbaum erfordern in Kauf genommen werden (wir versuchen, „alle“ Möglichkeiten auf der „gleichen“ Zeit). Polynomicaly veryfiable bedeutet, dass wir ein Zertifikat (C läßt es sein), die eine Lösung für das Eingangswort ist (lassen w sein). Zertifikat muss eine Polynomlänge Eingabelänge unter Berücksichtigung sein. Unsere Aufgabe ist es nur, um zu überprüfen, ob ein Zertifikat eine Lösung ist. Zum Beispiel in SAT (satisfyability Problem) ein Zertifikat ist eine korrekte Zuweisung (die nicht-deterministisch geraten ist).

So Sie beweisen, dass Ihr Problem in NP ist: Es existiert ein DTM, dass überprüft ein Paar (W, C), wobei w Eingangsnummer und seine c Faktoren sind. Sie müssen nur ein Konstrukt veryfier dass vervielfacht Faktoren in c und vergleicht sie mit w.