Il problema P/NP
Da sempre i computer sono stati utilizzati dall’uomo per risolvere problemi di qualsiasi tipo. Nell’ambito matematico se la cavano molto bene con i calcoli aritmetici, ma la matematica è ben altro che soli conti. Spesso la parte più difficile del lavoro è proprio convertire il problema in qualcosa che il computer sia in grado di risolvere.
Quindi, a volte, il computer è al servizio della matematica, altre volte avviene il contrario.
Uno dei problemi del millennio si trova al confine tra matematica e informatica.
Il problema riguarda gli algoritmi, gli scheletri matematici di cui sono fatti i programmi per computer; il concetto fondamentale è l’efficienza dell’algoritmo, cioè di quanti passi computazionali ha bisogno per ottenere una risposta per una data quantità di dati in ingresso.
Dall’antichità, i matematici consideravano risolto un problema se erano in grado di scrivere un algoritmo che portava a una risposta. Invece di usare la parola algoritmo, presentavano una formula risolutiva espressa in linguaggio simbolico. La formula era la soluzione, anche se non si aveva la certezza di una sua applicazione pratica.
Con l’inizio dell’era dei calcolatori questo modo di vedere le cose fu modificato, perché le formule troppo complicate per svolgere i calcoli a mano venivano fatte svolgere dai computer.
Questa tecnica, però, presentava qualche difficoltà: anche se il computer poteva cercare di far girare l’algoritmo, era troppo lento per arrivare al risultato.
Così iniziò la ricerca di algoritmi efficienti.
Dato un algoritmo è in generale semplice stimare quanto tempo impiegherà per risolvere un problema con un dato in ingresso di una certa grandezza. È ben più difficile ideare un algoritmo più efficiente se quello da cui partiamo si rileva inefficiente.
I primi studi sull’argomento portarono a una prima distinzione grossolana tra algoritmi efficienti e non. Se la lunghezza dell’elaborazione cresce con relativa lentezza al crescere della grandezza dell’input, l’algoritmo è efficiente e il problema è facile; se la lunghezza del calcolo cresce sempre più al crescere delle dimensioni dell’input, l’algoritmo è inefficiente e il problema è difficile.
Con questi presupposti, la richiesta del millennio è: fornire una dimostrazione rigorosa che esista almeno un problema difficile, oppure che, contrariamente all’esperienza, tutti i problemi sono facili.
Questo quesito è noto come problema P/NP, e nessuno ha idea di come risolverlo.
Un algoritmo è di classe P se ha un tempo di esecuzione polinomiale, cioè il numero di passi che richiede per trovare la risposta è proporzionale a una potenza fissa, come il quadrato della grandezza dei dati in ingresso. Se l’input è un numero, la “grandezza” è il numero delle sue cifre, non il numero stesso. Tutti questi tipi di algoritmo sono efficienti.
La classe NP è rappresentata dagli algoritmi che richiedono un tempo polinomiale non deterministico, cioè quale che sia il tempo di esecuzione richiesto possiamo verificare in tempo polinomiale che la risposta sia giusta. Trovarla può essere anche difficile, ma una volta trovata c’è un metodo facile per verificarne la validità.
Con queste definizioni e con la mancanza, ad oggi, di una dimostrazione rigorosa del problema, ci possiamo chiedere: esistono problemi difficili? Non potrebbe darsi che tutti problemi siano facili, se solo fossimo abbastanza intelligenti?
