Ridurre il problema fattorizzazione di interi ad un problema NP-completo

Question

sto lottando per capire il rapporto tra NP-intermedio e NP-completo. So che se P! = NP basato sul teorema di Ladner esiste una classe di linguaggi in NP, ma non in P o in NP-completo. Ogni problema in NP può essere ridotto ad un problema NP-completo, tuttavia non ho visto alcun esempio per la riduzione di un sospetto problema NPI (come fattorizzazione di interi) in un problema NP-completo. Qualcuno sa di qualsiasi esempio di questo o di un altro riduzione NPI-> NPC?

Answer 1

Ad esempio, v'è una riduzione classico ordinata di factoring a SAT che è anche una fonte di casi presunti "duri" SAT. Fondamentalmente uno usi EE idee per la moltiplicazione binario codificato nel circuito SAT. Pensare moltiplicazione binaria come aggiunta di una serie di multiplicands spostata a sinistra, ogni "mascherato" (ANDed) per i bit di un moltiplicatore. Le aggiunte possono essere eseguite da un circuito di somma binaria che è una serie di full adder.

Una laurea di talento potrebbe costruire questo algoritmo. Non so dove è stato proposto o attuato nella letteratura prima. Sarei interessato a sapere tutti i riferimenti.

Vedere per esempio soddisfare questa: un tentativo di Solving Primo fattorizzazione utilizzando Soddisfacibilità risolutori da Stefan Schoenmackers e Anna Cavender che depone in dettaglio. Anche il DIMACS SAT sfida a partire dalla fine del anni '90 avevano casi di factoring che sono stati generati da alcuni ricercatori, ma forse l'algoritmo non è stato redatto separatamente in un documento durante quel periodo.

Answer 2

Giusto per essere assolutamente chiaro, fattorizzazione di interi non è noto essere NP-intermedio, solo sospettato di essere sulla base della mancanza di una prova di NP-completezza o algoritmo polinomiale (nonostante un sacco di mettere il lavoro in entrambi). Non so di qualsiasi problema naturale (cioè non costruite dalla Ladner per la prova) che è sicuramente NP-intermedio se P e NP sono diversi.

D'accordo, dopo che dichiarazione di non responsabilità, Graph Isomorfismo è un altro probabile candidato per un naturale problema NP-intermedio. C'è una semplice riduzione polinomiale da esso per sottografo Isomorfismo - basta lasciare i grafici lo stesso! Grafico Isomorfismo è solo il caso particolare di sottografo Isomorfismo dove entrambi i grafici hanno la stessa dimensione. Il tocco finale è che sottografo Isomorfismo è NP-completo.

Oltre a questo, c'è sempre, naturalmente, la riduzione non-così-informativo promesso dal COOK- Levin Teorema , abbiamo saputo che qualsiasi problema NP-intermedio ha qualche non deterministica polinomiale macchina di Turing che decide, e siamo in grado di convertire questo in un'istanza di SAT (semplicemente per costruire il TM!).