[Algoritmi] np-completezza

[mistergks]

So che un problema L è np-completo se L appartiene ad NP e ad NP-HARD..
Ma qual è l importanza pratica di verificare che un algoritmo sia np-completo?

[mistergks]

Up

Inviato dal mio GT-I9003 con Tapatalk 2

[vendettaaaaa]

Se appartiene a quella classe di problemi, le possibili soluzioni algoritmiche a forza bruta, cioè sviluppate senza sfruttare particolari proprietà del sistema, sono intrattabili, cioè ci vogliono centinaia di anni di tempo di calcolo per risolverle.

[epimerasi]

So che un problema L è np-completo se L appartiene ad NP e ad NP-HARD..
Ma qual è l importanza pratica di verificare che un algoritmo sia np-completo?

I problemi np-completi sono i problemi piu` difficili da risolvere fra i problemi in NP.

"Piu' difficile" in senso formale: se venisse dimostrato che un problema np-completo ha una soluzione in tempo polinomiale, allora tutti problemi NP (non solo gli NP-completi) sarebbero risolvibili in tempo polinomiale (perche` passare da un problema np/completo ad un altro puo` essere fatto in tempo polinomiale).

Allo stesso modo dimostrare che un problema NP-completo NON puo` essere risolto in tempo polinomiale, sarebbe come dimostrarlo per tutti gli NP.

[epimerasi]

Se appartiene a quella classe di problemi, le possibili soluzioni algoritmiche a forza bruta, cioè sviluppate senza sfruttare particolari proprietà del sistema, sono intrattabili, cioè ci vogliono centinaia di anni di tempo di calcolo per risolverle.

In realta` questo e` possibile anche per algoritmi risolvibili in tempo polinomiale

[vendettaaaaa]

ma in particolar modo per gli np, per i quali non esistono proprio algoritmi senza bruteforce
Nel corso di algoritmi non siamo ancora arrivati a quella parte, ma a quanto ho capito quest'affermazione è sbagliata: il PEG Solitaire inglese è NP-completo ma ci sono algoritmi che risolvono il problema in 5 minuti.

[DanieleC88]

Nel corso di algoritmi non siamo ancora arrivati a quella parte, ma a quanto ho capito quest'affermazione è sbagliata: il PEG Solitaire inglese è NP-completo ma ci sono algoritmi che risolvono il problema in 5 minuti.

Anche SAT è NP-completo, ma il DPLL trova soluzioni in tempi accettabili, se l'input ha dimensioni ragionevoli.

Qui non stiamo parlando strettamente di tempo di esecuzione, ma del fatto che un problema NP-completo richiede tempo polinomiale su una TM non-deterministica per trovare una sua soluzione, e tempo polinomiale su una TM deterministica per verificare una sua soluzione.

Il fatto che richieda tempo polinomiale su una TM non-deterministica significa, all'atto pratico, che devi eventualmente esplorare tutto lo spazio di ricerca (tentare tutte le strade possibili) per trovare una soluzione.

Sono un po' arrugginito su questi temi, quindi correggetemi se dico castronerie. :D

[vendettaaaaa]

Ok, ripasserò dopo aver studiato meglio questa parte :D