come si sono dimostrati i primi problemi NP completi?

Question

Dalla voce di Wikipedia su NP-Complete:

" Il modo più semplice per dimostrare che un nuovo problema è NP-completo è prima quello di dimostrare che si trova in NP, e quindi di ridurre ad esso qualche problema noto di NP-completo "

Sono abbastanza sicuro di capirlo: se ho un problema, posso dimostrare che è NP-Complete se:

1. mostra che si trova in NP (una soluzione a il problema può essere verificato in tempo polinomiale su a macchina di Turing non deterministica)

2. Mostra che può esserci un problema già noto come NP-Complete "ridotto" al nuovo problema

Quindi, la mia domanda è: in che modo è stato dimostrato che i primi problemi NP completi sono NP-completi? Un tempo, l'insieme di problemi noti di NP-complete deve essere stato zero e ciò avrebbe reso impossibile il ricorso al passaggio 2 del processo sopra descritto.

Questo mi fa pensare che esiste un metodo di prova diverso di cui non sono a conoscenza. O quella, o forse l'intera proprietà NP completa viene "assunta" per alcuni problemi a causa della mancanza di una soluzione temporale polinomiale nota. (in realtà, dopo averlo scritto, non sarei sorpreso se fosse così, ma mi piacerebbe ricevere un feedback da un guru in entrambi i casi).

Answer 1

Teorema di Cook

La classe NP può essere definita come la classe di problemi decidibile da una macchina di Turing non deterministica in tempo polinomiale. Questo teorema mostra che SAT è NP completo codificando il funzionamento di qualsiasi macchina di Turing non deterministica con una formula booleana, in modo tale che la macchina accetti se e solo se tale formula è SODDISFABILE.

Storicamente parlando, la nozione di completezza NP è stata introdotta nel documento fondamentale di Richard Karp ( Riducibilità tra i problemi combinatori ), in cui ha definito la completezza NP, ha usato il teorema di Cook e in un colpo solo ha dimostrato 21 problemi NP-completi.

Answer 2

Per darti l'essenza della prova (che sono diverse pagine di duro lavoro su Computer e Intrattabilità di Garey & amp; Johnson ):

Qualsiasi problema computazionale può essere espresso come una macchina di Turing.

È possibile esprimere la macchina di Turing come un problema logico, soddisfacendo alcuni vincoli di complessità.

Pertanto, se è possibile risolvere il problema logico in tempo polinomiale, è possibile risolvere il problema della macchina di Turing in tempo polinomiale.

Questo (insieme ad alcune altre considerazioni) mostra che se è possibile risolvere il problema logico in tempo polinomiale, è possibile risolvere qualsiasi problema NP in tempo polinomiale. Trattandosi della definizione di NP completo, il problema logico è quindi NP completo e può essere utilizzato come base per altri problemi.

Il problema logico utilizzato è chiamato Soddisfacibilità (spesso abbreviato in SAT). Data una serie di clausole della forma (A o non-B o non-C) (clausole costituite da un numero qualsiasi di proposizioni e negazioni di proposizioni collegate da logiche o), esiste un'assegnazione di valori di verità alle proposizioni che rende tutto le clausole sono vere?

La completezza NP è una proprietà ben definita. L'unico motivo per cui potresti avere dei dubbi sul fatto che un problema sia NP-completo è che hai pensato di poter ridurre ad esso un altro problema NP-completo, ma non sei riuscito a trovare un problema conveniente o ottenere ancora una prova.

La domanda non è se esistono problemi NP-completi, o come dimostrare che un problema è NP-complete, ma cosa significa. Nessuno ha ancora prodotto un algoritmo a tempo polinomiale per risolvere un problema NP-completo e nessuno ha dimostrato che tale algoritmo non può esistere. Indipendentemente dal fatto che P = NP, non abbiamo certamente buoni algoritmi per risolvere qualsiasi problema NP-completo.

Questo è uno dei problemi del Millennio della Claypool Foundation, quindi se riesci a trovare una prova che ha sfuggito ad alcune persone molto brillanti per alcuni anni, ci sono un milione di dollari per te.