Problema del P vs NP

Francesco Scolz
13 giu
Tempo di lettura: 3 min

Buongiorno così!

Dopo settimane di stop, sono tornato con nuovo materiale pronto per voi

Oggi andremo a vedere un'altro dei millennial problems

Che chiaramente non penso neanche di andare a risolvere, bensì di presentare a voi in maniera semplice

Senza dilungarmi troppo però, incominciamo!

Dunque, cosa sono P e NP?

Sono due insiemi di problemi, che (per quello che ne sappiamo noi) sono ancora distinguibili

I problemi in P:

Sono i problemi più facili, come trovare il massimo di una lista o il percorso più veloce tra due punti
Si possono TROVARE le soluzioni in tempi Polinomiali (quindi del tipo A + Bn + Cn² ...)
Esempio: per trovare il massimo in una lista, passiamo per ogni elemento, tenendo traccia del massimo fino a quel punto. Passati tutti gli elementi possiamo essere sicuri che quello registrato per ultimo sia il massimo assoluto
Abbiamo passato N elementi, perciò la sua complessità di algoritmo è O(n), dove n è sia il numero di elementi, sia il numero di comparazioni e dunque operazioni

I problemi in NP:

Sono i problemi più difficili, come risolvere un sudoku o scomporre un numero in fattori primi
Si possono VERIFICARE le soluzioni in tempi Polinomiali (quindi del tipo A + Bn + Cn² ...)
Le soluzioni sono più difficili: bisogna andare quasi sempre a forza bruta, anche se ci sono semplificazioni possibili
Esempio: per scomporre un numero in fattori primi, proviamo i fattori uno per uno. Questo porta la complessità del problema a crescere di molto più aumentano i bit del numero scritto in binario (se non sai cos'è il sistema binario, clicca qui)
Se N è il numero in decimale, e n i bit necessari per scriverlo in binario, la sua complessità è pari a O(2^(n/2)), quindi segue O(2^n), un andamento esponenziale

Ok, un dubbio. Perché usiamo il numero di bit binari invece che il numero decimale nel secondo esempio?

Semplicemente, il sistema binario è quello usato dalle macchine computazionali (non per ultima, la macchina di Turing), che usa proprio 0 e 1, tradotti in segnali elettrici.

Così funzionano anche i nostri neuroni, semplificandola

Il sistema decimale è un sistema inventato dall'uomo, quando si contava ancora sulle nostre 10 dita delle mani

I problemi NP racchiudono in sé anche altri problemi, detti NP-completi

Questi sono i problemi dove la forza bruta è l'unica possibilità, e non c'è modo di semplificare l'operazione (pensiamo allo scoprire una combinazione di 4 numeri)

Già solo questo problema richiederebbe la prova di 10⁴ = 10000 tentativi

Pensate alle password, lunghe ed alfanumeriche...

Dunque, per riassumere:

I problemi in P sono "facili", dato che si possono risolvere in un tempo determinato (massimo di una lista)
I problemi in NP sono più difficili: si basano sulla forza bruta e su alcune semplificazioni (sudoku)
I problemi NP-completi sono i più difficili, dove non esistono semplificazioni possibili