P contro NP

Per esempio, se avete un problema e qualcuno vi dice "La risposta al vostro problema è l'insieme dei numeri 1, 2, 3, 4, 5", un computer può essere in grado, rapidamente, di capire se la risposta è giusta o sbagliata, ma può impiegare molto tempo perché il computer arrivi effettivamente a dire "1, 2, 3, 4, 5" da solo. Un altro esempio è la ricerca dei numeri primi. È facile controllare se un numero è primo, ma è molto difficile trovare quei numeri in primo luogo. Per alcune interessanti domande pratiche di questo tipo, non c'è modo di trovare rapidamente una risposta, ma se ci viene fornita una risposta, è possibile controllare, cioè verificare, la risposta rapidamente. In questo modo, i problemi NP possono essere pensati come degli indovinelli: può essere difficile trovare la risposta ad un indovinello, ma una volta che uno sente la risposta, la risposta sembra ovvia. In questo paragone (analogia), la domanda di base è: gli indovinelli sono davvero così difficili come pensiamo che siano, o ci manca qualcosa?

Poiché questo tipo di domande P contro NP sono così importanti dal punto di vista pratico, molti matematici, scienziati e programmatori di computer vogliono dimostrare la proposizione generale che ogni problema controllato rapidamente può anche essere risolto rapidamente. Questa domanda è abbastanza importante che il Clay Mathematical Institute darà 1.000.000 di dollari a chiunque riesca a fornire una prova o una spiegazione valida che la confuti.

Scavando un po' più a fondo, vediamo che tutti i problemi P sono problemi NP: è facile controllare che una soluzione sia corretta risolvendo il problema e confrontando le due soluzioni. Tuttavia, la gente vuole sapere il contrario: Esistono problemi NP diversi dai problemi P, o tutti i problemi NP sono solo problemi P? Se i problemi NP non sono davvero uguali ai problemi P (P ≠ NP), significherebbe che non possono esistere modi generali e veloci per risolvere quei problemi NP, per quanto ci si sforzi di cercare. Tuttavia, se tutti i problemi NP sono problemi P (P = NP), significherebbe che esistono nuovi metodi molto veloci per risolvere i problemi. Solo che non li abbiamo ancora trovati.

Poiché i migliori sforzi degli scienziati e dei matematici non hanno ancora trovato metodi generali e facili per risolvere i problemi NP, molte persone credono che esistano problemi NP diversi dai problemi P (cioè che P ≠ NP sia vero). Anche la maggior parte dei matematici crede che questo sia vero, ma attualmente nessuno lo ha dimostrato con un'analisi matematica rigorosa. Se si potesse dimostrare che NP e P sono la stessa cosa (P = NP è vero), ciò avrebbe un enorme impatto su molti aspetti della vita quotidiana. Per questo motivo, la questione di P rispetto a NP è un argomento importante e ampiamente studiato.

Supponiamo che qualcuno voglia costruire due torri, impilando rocce di massa diversa. Si vuole essere sicuri che ciascuna delle torri abbia esattamente la stessa massa. Ciò significa che si dovranno mettere le rocce in due mucchi che abbiano la stessa massa. Se si indovina una divisione delle rocce che si pensa possa funzionare, sarebbe facile controllare se si ha ragione. (Per controllare la risposta, si possono dividere le rocce in due mucchi, poi usare una bilancia per vedere se hanno la stessa massa). Poiché è facile controllare questo problema, chiamato "partizione" dagli informatici - più facile che risolverlo del tutto, come vedremo - non è un problema P. ^[]

Quanto è difficile da risolvere, vero? Se si inizia con solo 100 rocce, ci sono 2^{100-1}-1 = 633.825.300.114.114.700.748.351.602.687, o circa 6,3 x 10^{29} modi (combinazioni) possibili per dividere queste rocce in due pile. Se si potesse controllare una combinazione unica di rocce ogni giorno, ci vorrebbero 1,3 x 10^{22} o 1.300.000.000.000.000.000.000.000 anni di sforzo. Per fare un confronto, i fisici ritengono che l'universo abbia circa 1,4 x 10^{10} anni (450.000.000.000.000.000.000 o circa 4,5 x 10^{17} secondi, o circa un trilionesimo del tempo che ci vorrebbe per il nostro sforzo di ammassare rocce. Ciò significa che se si prende tutto il tempo che è passato dall'inizio dell'universo, bisognerebbe controllare più di duemila miliardi (2.000.000.000.000.000) di modi diversi di dividere le rocce ogni secondo, per controllare tutti i modi diversi.

Se si programmasse un computer potente, per testare tutti questi modi di dividere le rocce, si potrebbe essere in grado di controllare 1 , 000 , 000 {displaystyle 1,000,000} combinazioni al secondo utilizzando i sistemi attuali. Ciò significa che ci vorrebbero ancora 2 , 000 , 000 {displaystyle 2,000,000} computer molto potenti, funzionanti dall'origine dell'universo, per testare tutti i modi di dividere le rocce.

Tuttavia, potrebbe essere possibile trovare un metodo per dividere le rocce in due mucchi uguali senza controllare tutte le combinazioni. La domanda "P è uguale a NP?" è un'abbreviazione per chiedere se può esistere un metodo del genere.

Ci sono molti problemi NP importanti che la gente non sa come risolvere in un modo che sia più veloce del testare ogni possibile risposta. Ecco alcuni esempi:

• Un commesso viaggiatore vuole visitare 100 città guidando, iniziando e finendo il suo viaggio a casa. Ha una scorta limitata di benzina, quindi può percorrere solo un totale di 10.000 chilometri. Vuole sapere se può visitare tutte le città senza finire la benzina.
• Una scuola offre 100 classi diverse e un insegnante deve scegliere un'ora per l'esame finale di ogni classe. Per prevenire gli imbrogli, tutti gli studenti che frequentano una classe devono fare l'esame per quella classe alla stessa ora. Se uno studente frequenta più di una classe, allora tutti gli esami devono essere in un orario diverso. L'insegnante vuole sapere se può programmare tutti gli esami nello stesso giorno in modo che ogni studente possa fare l'esame per ciascuna delle sue classi.
• Un contadino vuole portare al mercato 100 angurie di massa diversa. Ha bisogno di imballare le angurie in scatole. Ogni scatola può contenere solo 20 chilogrammi senza rompersi. L'agricoltore ha bisogno di sapere se 10 scatole le basteranno per portare tutte e 100 le angurie al mercato. (Questo è banale, se non più di un'anguria pesa più di 2 kg allora se ne possono mettere 10 in ogni cassa, se non più di dieci angurie pesano più di 2 kg allora se ne può mettere una in ogni cassa, ecc. per una soluzione rapida; l'osservazione sarà la chiave di ogni soluzione rapida come questa o come il problema dell'insieme dei numeri).
• Una grande galleria d'arte ha molte stanze, e ogni muro è coperto da molti quadri costosi. Il proprietario della galleria vuole comprare delle telecamere per guardare questi quadri, nel caso in cui un ladro cerchi di rubarne qualcuno. Vuole sapere se 100 telecamere gli basteranno per assicurarsi che ogni quadro possa essere visto da almeno una telecamera.
• Il problema della cricca: Il preside di una scuola ha una lista di quali studenti sono amici tra loro. Vuole trovare un gruppo del 10% degli studenti che sono tutti amici tra loro.

Nell'esempio sopra, vediamo che con 100 {displaystyle 100} rocce, ci sono 2 100 {displaystyle 2^{100}} modi di partizionare l'insieme delle rocce. Con n {displaystyle n} rocce, ci sono 2 n {displaystyle 2^{n} combinazioni. La funzione f ( n ) = 2 n {displaystyle f(n)=2^{n} è una funzione esponenziale. E' importante per NP perché modella il caso peggiore del numero di calcoli che sono necessari per risolvere un problema e, quindi, il caso peggiore della quantità di tempo richiesto.

E finora, per i problemi difficili, le soluzioni hanno richiesto un numero di calcoli dell'ordine di 2 n {displaystyle 2^{n}}. Per ogni particolare problema, le persone hanno trovato modi per ridurre il numero di calcoli necessari. Si potrebbe trovare un modo per fare solo l'1% del numero di calcoli nel caso peggiore e risparmiare un sacco di calcoli, ma si tratta comunque di 0,01 × ( 2 n ) {displaystyle 0,01 volte (2^{n})} calcoli. E ogni roccia in più raddoppia ancora il numero di calcoli necessari per risolvere il problema. Ci sono intuizioni che possono produrre metodi per fare ancora meno calcoli producendo variazioni del modello: ad esempio 2 n / n 3 {displaystyle 2^{n}/n^{3}} . Ma la funzione esponenziale domina ancora come n {displaystyle n} cresce.

Considerate il problema della programmazione degli esami (descritto sopra). Ma supponiamo, poi, che ci siano 15000 studenti. C'è un programma per computer che prende gli orari di tutti i 15000 studenti. In un'ora esegue e produce un programma d'esame in modo che tutti gli studenti possano fare i loro esami in una settimana. Soddisfa un sacco di regole (nessun esame back-to-back, non più di 2 esami in un periodo di 28 ore, ...) per limitare lo stress della settimana degli esami. Il programma funziona per un'ora durante la pausa di metà trimestre e tutti conoscono il loro programma d'esame con un sacco di tempo per prepararsi.

L'anno successivo, però, ci sono 10 studenti in più. Se lo stesso programma viene eseguito sullo stesso computer, allora quell'ora diventerà 2 10 {displaystyle 2^{10} ore, perché ogni studente in più raddoppia i calcoli. Sono 6 {displaystyle 6} settimane! Se ci fossero 20 studenti in più, allora

2 20 {displaystyle 2^{20}} ore = 1048576 {displaystyle 1048576} ore ~ 43691 {displaystyle 43691} giorni ~ 113 {displaystyle 113} anni

Così, per 15000 {displaystyle 15000} studenti, ci vuole un'ora. Per 15020 {displaystyle 15020} studenti, ci vogliono 113 {displaystyle 113} anni.

Come potete vedere, le funzioni esponenziali crescono molto velocemente. La maggior parte dei matematici crede che i problemi NP più difficili richiedano un tempo esponenziale per essere risolti.

I matematici possono dimostrare che ci sono alcuni problemi NP che sono NP-Completi. Un problema NP-Completo è difficile da risolvere almeno quanto qualsiasi altro problema NP. Questo significa che se qualcuno trovasse un metodo per risolvere rapidamente qualsiasi problema NP-Completo, potrebbe usare lo stesso metodo per risolvere rapidamente ogni problema NP. Tutti i problemi elencati sopra sono NP-Completi, quindi se il venditore ha trovato un modo per pianificare il suo viaggio velocemente, potrebbe dirlo all'insegnante, e lei potrebbe usare lo stesso metodo per programmare gli esami. Il contadino potrebbe usare lo stesso metodo per determinare di quante scatole ha bisogno, e la donna potrebbe usare lo stesso metodo per trovare un modo per costruire le sue torri.

Poiché un metodo che risolva rapidamente uno di questi problemi può risolverli tutti, ci sono molte persone che vogliono trovarne uno. Tuttavia, poiché ci sono così tanti diversi problemi NP-Completi e nessuno finora ha trovato un modo per risolverne rapidamente anche uno solo, la maggior parte degli esperti ritiene che risolvere rapidamente i problemi NP-Completi non sia possibile.

Proprietà di base

Nella teoria della complessità computazionale, la classe di complessità NP-completa (abbreviata NP-C o NPC), è una classe di problemi con due proprietà:

• È nell'insieme dei problemi NP (tempo polinomiale non deterministico): Qualsiasi soluzione data al problema può essere verificata rapidamente (in tempo polinomiale).
• È anche nell'insieme dei problemi NP-duri: Quelli che sono difficili almeno quanto i problemi più difficili in NP. I problemi che sono NP-duri non devono necessariamente essere elementi di NP, anzi, possono anche non essere decidibili.

Panoramica formale

NP-completo è un sottoinsieme di NP, l'insieme di tutti i problemi decisionali le cui soluzioni possono essere verificate in tempo polinomiale; NP può essere definito equivalentemente come l'insieme dei problemi decisionali risolti in tempo polinomiale su una macchina. Un problema p in NP è anche in NP se e solo se ogni altro problema in NP si trasforma in p in tempo polinomiale. NP-completo doveva essere usato come aggettivo: i problemi della classe NP-completo erano come problemi NP+completi.

I problemi NP-completi sono studiati perché la capacità di verificare rapidamente le soluzioni di un problema (NP) sembra essere correlata alla capacità di risolvere rapidamente il problema (P). Si è trovato che ogni problema in NP è rapidamente risolto - come chiamato l'insieme di problemi P = NP:. Il singolo problema in NP-completo è risolto rapidamente, più velocemente di ogni problema in NP anch'esso risolto rapidamente, perché la definizione di un problema NP-completo afferma che ogni problema in NP deve essere rapidamente riducibile ad ogni problema in NP-completo (si riduce in tempo polinomiale). [1]

Esempi

Il problema della satirabilità booleana è noto per essere NP completo. Nel 1972, Richard Karp ha formulato 21 problemi che sono noti per essere NP-completi. Questi sono conosciuti come i 21 problemi NP-completi di Karp. Includono problemi come il problema della programmazione integrale, che applica tecniche di programmazione lineare ai numeri interi, il problema knapsack, o il problema della copertura dei vertici.