Dimostrare che il problema del factoring a è in NP

Question

Il tentativo di rispolverare la teoria di calcolo, ma non sono sicuro di soluzione a questo:

Prove that the problem of factoring α is in NP.

ho la sensazione che può essere correlato alla ricerca di un problema NP e trovare una riduzione al problema della fattorizzazione a.

Answer 1

Questo è semplice in realtà. Moltiplicazione è in P. NP è uguale a "controllare tutte le possibili soluzioni polinomiali dimensioni in parallelo". Se alfa è codificato come una stringa di bit di lunghezza n, i fattori lunghezza totale è al massimo n + c.

Quello che non si è "NP-completo". Non v'è alcun modo per trasformare un problema NP arbitraria in factoring.

Answer 2

Problema in P : è un problema, che è calcolabile da deterministico Macchina di Turing in tempo polinomiale problema in NP : è un problema, è thas polynomicaly veryfiable da deterministico Macchina di Turing.

In NP, stiamo usando non determinismo in modo tale che si richiede solo un ramo di un albero computazione da accettare (cerchiamo "tutti" possibilità al momento "stesso"). mezzi veryfiable Polynomicaly, che abbiamo un certificato (lascia che sia c), che è una soluzione per la parola di ingresso (lascia che sia w). Certificato deve essere di lunghezza polinomiale considerando la lunghezza di ingresso. Il nostro compito è solo quello di verificare se un certificato è una soluzione. Ad esempio, in SAT (problema satisfyability) un certificato è una corretta assegnazione (che è indovinato non deterministico).

Così si dimostra che il problema è in NP: Esiste un DTM che verifica una coppia (w, c), dove w è il numero di input e C sono i suoi fattori. È necessario solo costruire un veryfier che i fattori moltiplica in C e lo confronta con w.