Il problema P contro NP invecchiato
Quindi, cosa succede allora, è il problema P contro NP?
Per la cronaca, lo status quo è che P NP NP.
P (tempo polinomiale) si riferisce alla classe di problemi che possono essere risolti da un algoritmo in tempo polinomiale. I problemi nella classe P possono variare da qualsiasi cosa semplice come la moltiplicazione a trovare il numero più grande in un elenco. Sono l’insieme relativamente “più facile” di problemi.
NP (tempo polinomiale non deterministico) si riferisce alla classe di problemi che possono essere risolti in tempo polinomiale da un computer non deterministico., Questo è essenzialmente un altro modo per dire “Se ho una potenza di calcolo illimitata (cioè tutti i computer di cui ho bisogno), sono in grado di risolvere qualsiasi problema al massimo nel tempo polinomiale”. Più intuitivamente, tuttavia, si riferisce alla classe di problemi che attualmente non ha modo di trovare una risposta abbastanza rapida (tempo polinomiale), MA può essere rapidamente verificata (in tempo polinomiale) se si fornisce la soluzione al problema. Il termine verificato qui significa che si è in grado di verificare che la soluzione fornita sia effettivamente corretta.
Chiaramente, in base alla definizione di cui sopra, P NP NP., Diamo un’occhiata a un esempio per illustrare questo problema astratto.
Uno degli esempi più comuni ma efficaci è il Sudoku. Data una griglia Sudoku irrisolta (9 x 9 per esempio), ci vorrebbe un algoritmo una discreta quantità di tempo per risolverne uno. Tuttavia, se la griglia 9 x 9 aumenta a una griglia 100 x 100 o 10.000 x 10.000, il tempo necessario per risolverlo aumenterebbe esponenzialmente perché il problema stesso diventa significativamente più difficile., Tuttavia, data una griglia Sudoku risolta (di 9 x 9), è abbastanza semplice verificare che la soluzione particolare sia effettivamente corretta anche se la dimensione scala a 10.000 per 10.000. Sarebbe più lento, ma il tempo per controllare una soluzione aumenta a un ritmo più lento (polinomialmente).
Ci sono molti altri problemi NP là fuori, incluso il problema dello zaino e il problema dei venditori ambulanti, e sono simili in quanto sono difficili da risolvere ma veloci da verificare., Il problema fondamentale che stiamo cercando di risolvere qui è:
Essere in grado di riconoscere rapidamente le risposte corrette NP significa che esiste anche un modo rapido per trovarle?
Se è così (cioè P=NP), questo potrebbe cambiare notevolmente il modo in cui guardiamo questi problemi NP perché ciò significa che c’è un modo rapido per risolvere tutti questi problemi, solo che non siamo stati in grado di capire come, ANCORA.
Se questo non è abbastanza complicato, accendiamolo.,
Tra questi problemi NP, esiste un re di tutti i problemi che i ricercatori chiamano problemi NP-Completi. Formalmente, sono un insieme di problemi a ciascuno dei quali qualsiasi altro problema NP può essere ridotto (affrontato di seguito) in tempo polinomiale e la cui soluzione può ancora essere verificata in tempo polinomiale. Ciò significa che qualsiasi problema NP può essere trasformato in un problema NP-Completo.
Informalmente, sono il “più difficile” dei problemi NP., Quindi se un qualsiasi problema NP-Completo può essere risolto in tempo polinomiale, allora ogni problema NP-Completo può essere risolto in tempo polinomiale, e ogni problema in NP può essere risolto in tempo polinomiale (cioè P=NP). L’esempio più famoso sarebbe il problema dei venditori ambulanti.
esiste anche una serie di problemi che hanno chiamato NP-Hard problemi., Questi problemi sono almeno duri quanto i problemi NP, ma senza la condizione che richiede che sia risolto in tempo polinomiale. Ciò suggerisce che i problemi NP-Hard potrebbero non essere necessariamente parte della classe NP. Un esempio potrebbe essere risolvere una scacchiera-dato uno stato di una scacchiera, è quasi impossibile dire se una determinata mossa allo stato dato, è in realtà la mossa ottimale. Formalmente, non esiste un algoritmo di tempo polinomiale per verificare una soluzione a un problema NP-Hard.,
Se mettiamo insieme i due, un problema NP-Completo implica che sia NP-Hard, ma un problema NP-Hard NON implica che sia NP-Completo.
Definizione di NP-Completezza
Un problema L, è NP-Completo se:
- L è NP-Duro
- L appartiene a NP
Lo schema seguente (messa a fuoco sul lato sinistro) dovrebbe rendere le cose più chiare.,
Wait, what does it mean by reducing A to B?
Reduction forms the crux of NP-Completeness.,
Informalmente, un problema L1 può essere ridotto a un altro problema L2 se:
- istanza di L1 può essere modellato come un’istanza di L2
- La soluzione a quest’ultimo fornisce una soluzione per l’ex e viceversa
Per capire questo intuitivamente, si può pensare ad esso come tale:
Se L1 è riducibile a L2, L1 deve essere PIÙ duro come L2. Al contrario, L2 deve essere ALMENO duro come L1.
Matematicamente, questo è indicato come: L1 ≤p L2 (letto come “L1 è polinomialmente riducibile a L2”).,
