Beweisen Sie, dass das Problem der Faktorisierung α 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 in Zusammenhang stehen können und eine Reduktion auf das Problem der Faktorisierung von α finden.

Answer 1

Das ist eigentlich einfach. Multiplikation ist in P. NP ist das gleiche wie "alle möglichen polynomialen Lösungen parallel prüfen". Wenn Alpha als eine Länge von n Bitstring codiert ist, ist die Gesamtlänge der Faktoren höchstens n + c.

Was es nicht ist, ist "NP-vollständig". Es gibt keine Möglichkeit, ein beliebiges NP-Problem in Factoring umzuwandeln.

Answer 2

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

In NP verwenden wir Nichtdeterminismus so, dass wir nur einen Zweig eines Berechnungsbaums akzeptieren müssen (wir versuchen "alle" Möglichkeiten zur "gleichen" Zeit). Polynomisch sehr brauchbar bedeutet, dass wir ein Zertifikat haben (sei es c), das ist eine Lösung für das Eingabewort (lass es w sein). Das Zertifikat muss eine Polynomlänge haben, die die Länge der Eingabe berücksichtigt. Unsere Aufgabe besteht lediglich darin, zu überprüfen, ob ein Zertifikat eine Lösung darstellt. Zum Beispiel ist in SAT (Befriedigungs-Problem) ein Zertifikat eine korrekte Zuordnung (die nichtdeterministisch geschätzt wird).

So beweisen Sie, dass Ihr Problem in NP ist: Es gibt ein DTM, das ein Paar (w, c) überprüft, wobei w Eingabezahl und c seine Faktoren sind. Sie müssen nur einen sehr fiktiven Konstruktor konstruieren, der die Faktoren in c multipliziert und mit w vergleicht.