Come facciamo a sapere se un problema è più difficile in NP

Puoi leggere l'originale "1 problema più difficile" nel link . Ciò include uno schizzo di una dimostrazione che il problema è, in effetti, NP-completo.

Il problema è la soddisfacibilità booleana. Data una complessa espressione booleana, possiamo trovare un insieme di input che lo renderà vero? È facile vedere che il problema è in NP (data una possibile risposta, basta collegarla e valutarla).

Andare dall'altra parte è più difficile. Ecco l'idea di base. Dato qualsiasi problema in NP, è possibile progettare una macchina non deterministica che risolverebbe il problema in tempo polinomiale e produrrebbe un sì o un no. (Questo è ciò che significa essere in NP. Si noti che non possiamo in realtà costruire macchine non deterministiche, ma possiamo ancora teoricamente progettarle.) Dato il design della macchina possiamo quindi progettare un Booleano espressione che è solo un fattore polinomiale più grande che genererà vero / falso a seconda di ciò che la macchina non deterministica avrebbe prodotto. Pertanto, se avessimo un algoritmo del tempo polinomiale per rispondere al problema di soddisfacibilità booleana, potremmo risolvere qualsiasi problema NP in tempo polinomiale.

Ovviamente, una volta che hai un problema NP-completo, possiamo poi dimostrare che potrebbero essere utilizzati altri problemi NP per risolvere quella catena a margherita per trovare altri problemi NP-completi. Ma prima devi trovarne uno, e la soddisfazione booleana è stata la prima.

EDIT: Questa sembra essere una domanda simile (supponendo che la domanda riguardi la storia, non la "durezza"): Stack Overflow - I primi NP completano i problemi

Le macchine di Turing sono importanti perché sono considerate un modello di calcolo che si applica essenzialmente a qualsiasi computer (eccetto forse computer quantistici) link così ci aiutano a studiare il calcolo.

È passato un po 'di tempo da quando ho studiato la teoria della complessità, ma cercherò di spiegarlo in modo più dettagliato:

NP è tempo polinomiale non deterministico. Questo è il problema che può essere risolto in tempo polinomiale usando una macchina di Turing non deterministica. Il non-determinismo in questa affermazione implica che la macchina può esplorare contemporaneamente diverse soluzioni.

Il concetto di "tempo" è il numero di passaggi di calcolo in funzione della lunghezza dell'input. (poiché la lunghezza dell'input va all'infinito e ignora eventuali fattori costanti).

Dovrai esaminare il modello di una macchina di Turing per avere un'idea migliore di cosa si intende per lunghezza di input e passaggi.

E così, ci sono molti problemi nella classe di complessità NP, alcuni dei quali veramente facili. Alcuni di loro "difficili". Sono difficili perché non esiste una macchina deterministica, un tempo polinomiale, un algoritmo per risolverli. Sono anche molto interessanti perché se una di esse può essere risolta in tempo polinomiale su una macchina di Turing deterministica allora tutte di esse possono essere

Quando fai una dimostrazione formale per NP-completezza devi mostrare:

1. Che il problema è in NP. Quello che mostri è una macchina di Turing non deterministica che ha risolto il problema.
2. Che se è possibile risolverlo in tempo polinomiale su una macchina di Turing deterministica, allora è possibile risolvere qualche altro problema NP-completo in tempo polinomiale su una macchina di Turing deterministica. Lo fai tramite riduzione - trasformando un problema in un altro in un numero di passaggi che è una funzione polinomiale dell'input. Questo dimostra che è altrettanto difficile da risolvere quanto l'altro problema.

Penso di aver capito bene :-) Spero che abbia senso.