Post on 25-Jul-2020
23-04-2012
1
Complessita’ computazionale ed il problema P / NP
Fondamenti di Informatica 2011/12
Lucchetto con combinazione (3 numeri tra 0 e 39) Perche’ e’ sicuro? (escludendo che lo si rompa)
Combinazione di 3 numberi 0-39… Un ladro dovrebbe provare
403 = 64,000 combinazioni
23-04-2012
2
Tempo esponenziale
Tempo 2n per risolvere instanze di “taglia” n
Da tener presente:
Per n =300, 2n > numero di atomi dell’universo.
Incrementando n di 1 ! running time raddoppia!
Soddisfacibilita’ di formule Booleane
" Esiste un assegnamento che la rende vera? " E se abbiamo 100 variabili? " 1000 variabili? " Quanto impiegheremmo per trovare
l’assegnamento che rende vera la formula?
(A + B + C) ! (D + F + G) ! (A + G + K) ! (B + P + Z) ! (C + U + X)
! = and + = or A = not A
23-04-2012
3
Esistono numerosi problemi computazionali la cui soluzione richiede “trovare un ago in un pagliaio”….
CLIQUE Problem " In questo social network,
esiste una CLIQUE con 5 o piu’ studenti?
" CLIQUE: Gruppo di studenti, in cui ogni coppia di studenti sono amici
" Qual e’ un buon algoritmo per determinare clique?
" In che misura l’efficienza di tale algoritmo dipende dalla taglia della rete e della clique cercata?
23-04-2012
4
Il problema di “spargere la voce” " Social network " Ogni nodo rappresenta uno
studente " Due nodi sono connessi da un
arco se gli studenti sono amici " Anna comincia a mettere “voci in
giro” " La “voce” raggiungera’ Benjamin? " Suggerite un algoritmo per
rispondere alla domanda " Come cresce la complessita’
rispetto alla taglia della rete? " I server della “rete” devono
risolvere tale problema continuamente.
Ricerca esaustiva / Esplosione Combinatoriale
Algoritmi Naïve per molti problemi tipo “ago nel pagliaio” finiscono per testare tutte le possibili soluzioni ! running time esponenziale.
" Frequentissimo nell’universo computazionale
" E’ possibile trovare algoritmi migliori (come per “Spargere la Voce”)? Per es., running time O(n2).
23-04-2012
5
Armonia di gruppo
Dato un Social network di n studenti.
Dove gli archi corrispondono a coppie di studenti che NON vanno d’accordo.
Decidi se esiste un insieme di k studenti che costituisca un gruppo in armonia (ognuno va d’accordo con ognuno).
E’ il problema della Clique mascherato!
Il commesso viaggiatore (il problema dei corrieri UPS)
" Input: n locazioni e tutte le distanze tra coppie di punti, e una lunghezza k
" Scopo: decidere se esiste un modo per visitare tutte le locazioni percorrendo in totale una distanza <= k
23-04-2012
6
Il problema dell’Orario
" Input: n studenti, k corsi, liste degli studenti in ogni corso, m possibili orari per gli esami finali
" “Conflitto”: uno studente e’ in due corsi con l’esame programmato alla stessa ora
" Scopo: decidere se esiste la possibilita’ di programmare l’orario con al piu’ 100 conflitti?
Il problema P / NP " P: problemi per i quali e’ possibile trovare una soluzione
in tempo polinomiale (nc dove c e’ una costante e n e’ la “taglia dell’input”). Esempi: “ricerca binaria”, “Spargi la voce”
" NP: problemi per i quali una buona soluzione puo’ essere verificata in tempo nc. Esempi: Soddisfacibilita’ Booleana, Commesso Viaggiatore, Clique, Orario
" Domanda: Vale P = NP?
(Nota: Indipendente dal Modello computazionele --- Turing-Post, pseudocodice, C, Java, etc.)
23-04-2012
7
Problemi NP-completi
I Problemi “piu’ difficili” nella classe NP # Se uno di essi in P allora ogni problema in NP
e’ anche in P.
Esempi: Soddifacibilita’, Commesso Viaggiatore, Clique,
Orario, …. e molti molti altri ancora (migliaia)
Come e’ possibile provare che tali problemi sono “I piu’ difficili”?
“Riduzione”
“Datemi un punto d'appoggio, ed io muoverò la Terra.”
– Archimedes (~ 250BC)
“Se mi date un algoritmo polinomiale per il problema della Soddifacibilita’ delle Formule Boolean, Vi darò un algoritmo polinomiale per ogni problema in NP.” --- Cook, Levin (1971)
“Ogni problema in NP è un problema di soddisfacibilità “mascherato”
23-04-2012
8
Cosa fare con I problemi NP-completi
1. Euristiche (algoritmi che producono soluzioni ragionevoli per istanze reali)
2. Algoritmi di Approssimazione (producono soluzioni sub-ottimali, ma con la possibilità di garantire il massimo margine di sub-ottimalità)
Teoria della Complessità Computazionale: Studio dei problemi computazionalmente difficili.
" Studio dei processi ! focus sulla difficoltà computazionale
Una nuova prospettiva?
23-04-2012
9
Esempio 1: Economia Teoria degli equilibri:
" Input: n agenti, ognuno con un portafoglio iniziale (beni, denaro, etc.) e con delle preferenze (funzione per misurare il guadagno)
" Equilibrio: sistema di prezzi tale che per ogni bene, domanda = offerta.
" Equilibrio esiste [Arrow-Debreu, 1954]. Gli Economisti assumono che i mercati lo trovino (come una “mano invisibile”)
" Ma, non e’ noto alcun algoritmo efficiente per calcolarlo. Come fa il mercato a computarlo?
Esempio 2: Problema della Fattorizzazione
Dato un numero n, trova due numberi p, q (diversi da 1) tali che n = p x q.
Come possiamo risolverlo?
Infatti: Si “assume” che tale problema sia “difficile”. E’ alla base di gran parte della crittografia.
23-04-2012
10
Esempio 3: Quantum Computation
" Principio fondamentale della meccanica quantistica: quando una particella va da A a B, usa tutti i possibili cammini allo stesso tempo
" [Shor’97] Possiamo usare il comportamento quantistico per fattorizzare interi in maniera efficiente (e “rompere” protocolli crittografici)
" E’ possibile costruire un computer quantistico, o la meccanica quantistica non descrive correttamente il nostro mondo fisico?
A B Peter Shor
Esempio 4: Intelligenza Artificiale
Qual’e’ la complessita’ computazionale di problemi quali riconoscimeto del linguaggio, giocare Ottimamente a scacchi?
Etc. etc.
Un possibile dimostrazione che il cervello non e’ un computer: Mostrare che esso continuamente risolve problemi che “necessariamente” (dimostrato) richiedono tempo esponenziale su un computer
23-04-2012
11
Perche’ la relazione P / NP e’ un problema da $1.000.000? " Se P = NP allora soluzioni “brillanti” diventano la norma
(best schedule, best route, best design, best math proof, etc…)
" Se P " NP allora sappiamo qualcosa di nuovo e fondazionale non solo rispetto alla scienza dei computer (analogo a “Niente viaggia piu’ veloce della luce”).
Altre implicazioni: Crittografia (uso pratico della complessità computaz. )