Controllare è più facile che trovare?
Trovare una soluzione a un problema dovrebbe essere più difficile che controllare che una soluzione sia corretta. Sembra ovvio se hai mai risolto un puzzle di sudoku, o risolto un cubo di Rubik, o giocato una partita a scacchi. Ma questa affermazione, per quanto intuitiva, ci porta direttamente a una delle domande matematiche più profonde poste dalla nostra civiltà.
I problemi di tempo polinomiale non deterministico (o NP) sono quelli in cui è possibile verificare facilmente che una risposta sia corretta., Al contrario, i problemi del tempo polinomiale (o P) sono quelli
in cui trovare la risposta è facile. Se riesci a trovare la risposta, hai controllato che fosse corretta, quindi ogni problema in P è anche in NP. Diciamo che P è una sottoclasse di NP. Tuttavia, non sappiamo se c’è un problema particolare in NP che non è in P, e questo è ciò che chiamiamo il problema P vs NP.
Il problema P vs NP è uno dei problemi irrisolti più centrali in matematica e informatica teorica. C’è anche un premio Clay Millennium che offre un milione di dollari per la sua soluzione., Tuttavia, ci sono probabilmente modi molto più semplici per diventare un milionario che risolvere P vs NP!
Recentemente c’è stato un ronzio quando qualcuno ha preteso di risolverlo su arXiv, anche se è stata trovata rapidamente una lacuna nella dimostrazione. Dato il recente interesse per il problema e il suo posto centrale nella matematica, ne discuto nel blog di questa settimana.
Sudoku
Se ti viene dato un puzzle di Sudoku compilato in un giornale, potresti buttarlo nel cestino. Ma se lo volessi, potresti scansionare le righe, le colonne e 3 x 3 celle per dire che è una soluzione valida: ciascuno di 1, 2, … , 9 deve verificarsi esattamente una volta., Questo è analogo a NP, in quanto è relativamente facile verificare se una soluzione è corretta.
Tuttavia, se ti do un puzzle di Sudoku parzialmente riempito, può essere difficile trovare la soluzione. Questa è la gioia e la sfida di questo tipo di puzzle. Quindi essere in NP non sembra immediatamente implicare che il problema abbia una soluzione facile da trovare. Questa intuizione è al centro del problema P vs NP.
Formulazione precisa
Per comprendere P e NP in modo più preciso, dobbiamo comprendere meglio gli algoritmi e misurare la loro velocità. I problemi sono posti con alcuni input e output fissi SÌ o NO. L’input è una data lunghezza, ad esempio n, dove n è un numero intero positivo. Questo rappresenta il numero di bit necessari per esprimere l’input. Un algoritmo è un metodo o una procedura per risolvere un problema. Gli algoritmi forniscono istruzioni in ogni fase di un calcolo e devono terminare., I passaggi potrebbero essere secondi, millisecondi o qualche altro intervallo di tempo fisso che dipende dal problema.
La complessità di un problema è il tempo minimo di esecuzione del caso peggiore su tutti i possibili algoritmi che risolvono il problema in funzione della lunghezza dell’input. In altre parole, misura quanto tempo ci vuole per risolvere il problema con l’algoritmo più veloce ma con l’input del caso peggiore.
Un problema è risolvibile in tempo polinomiale se dato un input di lunghezza n, la sua complessità è limitata sopra dalla funzione polinomiale nm per alcuni interi non negativi m., L’insieme di tutti i problemi risolvibili in tempo polinomiale è indicato da P.
Essere in P non significa necessariamente che il problema sia fattibile. Ad esempio, se occorrono passaggi n1000 per eseguire l’algoritmo, allora sarà irrimediabilmente lento anche per piccoli n. I problemi polinomiali non deterministici (o NP) sono quelli in cui è possibile verificare se la risposta SÌ è corretta in tempo polinomiale.
NP-hardness
Un problema è NP–hard se un algoritmo in tempo polinomiale implicherebbe un algoritmo in tempo polinomiale per ogni problema in NP. Quindi, se un problema NP-difficile fosse in P, allora P = NP., I problemi NP-hard sono almeno duri come qualsiasi problema in NP. Un problema NP-completo è uno che è NP-hard e in NP.
Un classico problema NP-completo è trovare un ciclo di Hamilton. Per questo, supponiamo di avere una rete di città collegate da strade. Il problema è visitare ogni città usando le strade (non sono ammessi aerei!) e tornare alla partenza. Questo sembra facile per un piccolo numero di città, ma se ti sono state date centinaia di loro allora diventa difficile., Migliaia di altri problemi NP-completi sono noti derivanti dalla teoria dei grafi, dalla teoria dei numeri, dalla geometria e da altre aree della matematica e dell’informatica.
Qual è la risposta, davvero?
Se dovessi scommettere, allora presumerei che P non sia uguale a NP, e penso che la maggior parte degli esperti sarebbe d’accordo. Dovremmo essere terribilmente stupidi per non vedere come tutte le migliaia di problemi NP-completi non abbiano un algoritmo del tempo polinomiale. Ma come specie, dumb è la nostra posizione predefinita, quindi nessuno può dire quale sia la risposta con certezza al 100%.,
La cosa interessante del problema P vs NP è che indica quanto sia limitata la nostra comprensione nel dimostrare che alcuni problemi non hanno soluzioni veloci. Questo fa parte di un tema più ampio nel campo della teoria della complessità computazionale, che studia dozzine di altre classi di complessità. Scopri lo zoo complessità per un elenco di queste classi. Per la maggior parte, è aperto a mostrare che varie classi di complessità (spesso esotiche) sono sottoclassi appropriate l’una dell’altra. Ad esempio, non è noto se NL sia una sottoclasse corretta di P, e non sappiamo se FPT sia una sottoclasse corretta di W.,
Indipendentemente dalla sua veridicità, è probabile che il problema P vs NP rimanga aperto per qualche tempo. A meno che non sia dimostrato che P = NP, Sudoku rimane sicuro.
Antonio Bonato