Problemi facili, difficili,
impossibili……
ovvero
Che cosa si può fare (o non si può
fare) con un calcolatore
Simona Ronchi Della Rocca
Università di Torino
Dipartimento di informatica
INRIM, 25 settembre 2014
1
Sommario
Problemi risolubili e non risolubili
(a volte è impossibile…)
Problemi trattabili e intrattabili
(a volte è troppo costoso…)
P=NP?
(a volte non sappiamo dire…)
Soluzioni parziali
2
Che cosa è un problema?
Ci restringiamo qui alla classe dei problemi che
si possono comunicare ad un computer, cioè
alla classe dei problemi risolubili per mezzo di
un algoritmo.
Algoritmo:
Sequenza di regole deterministiche
Programma:
Algoritmo scritto in un formalismo leggibile
dal calcolatore (linguaggio di programmazione)
3
Esempi di algoritmi
ricetta di cucina
istruzioni per l’uso della lavatrice
regole per moltiplicare tra loro due numeri
………..
4
Problema algoritmico
Un problema algoritmico è definito da:
Insieme degli input (dati di ingresso)
ammissibili
L’insieme degli output (risultati) desiderati
in funzione dell’input
5
Problemi algoritmici:
esempi
Problema della Primalità:
Input:un numero intero positivo n
Output: “si” se n è primo, “no” altrimenti
(un numero è primo se è divisibile solo per 1 e per se’
stesso)
6
Esempi
Problema dell’Ordinamento
Input: una lista di parole in una lingua prefissata
Output: una lista di parole, che contiene tutte le
parole della lista in input, ma in ordine
alfabetico
7
Esempi
Problema del Fattoriale
Input: un numero naturale n
Output: n! = 1  2 …  n
8
Esempi
Problema del Commesso Viaggiatore
Input: una carta stradale, dove sono indicate le
lunghezze dei collegamenti da città a città,
due città A e B, e un numero n
Output: “si” se esiste un itinerario da A a B che
tocchi tutte le città della carta di lunghezza
minore o uguale a n, “no” altrimenti
9
Esempi
Problema della Piastrellatura
Input: n tipi diversi di piastrelle
(es.
)
Output: “si” se è possibile, con quante piastrelle vogliamo
di questi tipi, piastrellare ogni stanza associando le
piastrelle in modo che i colori confinanti coincidano,
“no” altrimenti.
10
Esempi
Problema della Fermata
Input: un programma P per il calcolatore, scritto
in un qualunque linguaggio di programmazione, e
un dato di input per P
Output: “si” se l’esecuzione di P su quel dato di
ferma, “no” altrimenti
11
Problemi risolubili e
non risolubili
Un problema è risolubile se esiste un algoritmo
che, per ogni istanza dei dati di input, produce
l’output voluto.
Un problema è non risolubile se non esiste un
algoritmo in grado di risolverlo.
12
Problemi risolubili e
non risolubili
Il problema della primalità è risolubile dal seguente
algoritmo:
1.
2.
3.
4.
Se n=1, rispondi NO e FINE. Altrimenti va al punto 2.
Se n=2, rispondi SI e FINE. Altrimenti va al punto 3.
Poni p=2.
Se p divide n, allora rispondi NO e FINE. Altrimenti
va al punto 5.
5. Incrementa p di 1. Se p=n, rispondi SI e FINE,
altrimenti va al punto 4.
13
Problemi risolubili e
non risolubili
Tra i problemi elencati, il problema della
piastrellatura e quello della fermata non sono
risolubili
Per ognuno di questi si dimostra che non può
esistere un algoritmo che lo risolva
(l’esistenza della soluzione implica una
contraddizione logica)
14
Dimostrazione della non
calcolabilità del problema
della fermata
Programma = lista finita di simboli su un
alfabeto dato
Scegliamo un linguaggio di
programmazione, e consideriamo tutti i
programmi con input e output numerici
(numeri naturali)
I programmi sono infiniti, ma numerabili,
cioè esiste una corrispondenza
biunivoca tra questi e i numeri naturali
(0,1,2,3…)
15
SCHEMA DELLA DIMOSTRAZIONE
Lista di tutti i programmi: P0 P1 P2P3……
Indichiamo con Pi(j) il risultato (se esiste)
dell’esecuzione del programma i sul dato j
Dimostriamo che non è calcolabile il problema
cosí definito:
ALT(i) = 1 se Pi(i) si ferma, 0 altrimenti
La non-calcolabilità di ALT implica la non
calcolabilità del problema della fermata.
16
Assumiamo per assurdo che ALT sia calcolabile,
allora esiste il programma SCAMBIA con questo
comportamento:
SCAMBIA(i) = 1 se ALT(i) = 0, NON SI FERMA
altrimenti
SCAMBIA = Pe, per un dato e
QUALE E’ IL RISULTATO DI Pe(e)?
Pe(e) =1 se ALT(e) = 0
(cioè se Pe(e) non si ferma),
Pe(e) NON SI FERMA altrimenti
(cioè se Pe(e) si ferma)
ASSURDO!!!!
Quindi ALT non è calcolabile.
CVD17
Attenzione!!!
La definizione non risolubilità è
ASSOLUTA
Non dipende dalla potenza del
computer usato o dalle risorse a
disposizione.
Un problema non risolubile
rimarrà tale sempre!
18
Prima suddivisione
problemi:
non risolubili
risolubili
19
Complessità di un
algoritmo
La complessità di un algoritmo misura
quanto costa, in termini di risorse di
tempo (e spazio), l’esecuzione
dell’algoritmo.
20
Complessità di un
problema
Un problema può avere diversi algoritmi
che lo risolvono, e con differenti
complessità. Siamo interessati alla
complessità minima, cioè alla minima
quantità di risorse di tempo (e spazio)
necessaria per l’esecuzione di un
algoritmo che risolva il problema dato.
21
Come misurare?
 La quantità di risorse dipende dai dati di
input (per calcolare il fattoriale di n
dobbiamo fare tante moltiplicazioni quanto è
il valore di n)
 Un problema è definito per ogni possibile
valore di input
 Come usciamo dal paradosso?
22
Misurazioni asintotiche
La complessità di un algoritmo (programma) è una
funzione che misura come varia la quantità di tempo
e/o spazio necessari per eseguirlo al variare della
dimensione dei dati in ingresso.
La complessità di un problema è la minima complessità
di un algoritmo che lo risolva.
 Esempio: L’algoritmo che risolve il problema del
fattoriale fa n operazioni di moltiplicazione, se l’input
è n, quindi la sua complessità in tempo è lineare nella
dimensione dell’input.
23
Esempio: il problema dell’ordinamento
I primi algoritmi disegnati avevano complessità
in tempo dell’ordine di n2
Si sono trovati poi algoritmi che risolvevano il
problema in tempo dell’ordine di n  log(n).
Si è poi dimostrato che la complessità minima
per il problema dell’ordinamento è proprio
n  log(n).
24
Quanto si è risparmiato?
n
n2
n  log n
2
4
2
3
9
6
10
100
100
40
10000
1000
25
Complessità polinomiale e
esponenziale
Sia n la dimensione dei dati.
Un algoritmo ha:
 Complessità polinomiale se la sua funzione di
complessità è maggiorata da c  nk, per qualche c e k
costanti
(si dice che la complessità appartiene a O(nk))
 Complessità esponenziale se questa è maggiorata da
c  kn, per qualche c e k costanti
(si dice che la complessità appartiene a O(kn ))
26
Complessità polinomiale e
esponenziale
n
n2
2n
2
4
4
3
9
8
10
100
1024
100
10000
*
* maggiore del numero di microsecondi trascorsi dal
BigBang!
27
Brutte notizie…….
Se un algoritmo ha complessità dell’ordine di 2100, poiché
tale numero è maggiore di quello dei miscosecondi
trascorsi dal BigBang, non possiamo materialmente
eseguirlo: dovremo attendere un tempo praticamente
infinito prima di poter ottenere il risultato.
Questo non dipende dalla velocità di calcolo del
calcolatore su cui l’algoritmo viene eseguito!
28
Problemi trattabili e intrattabili
 Un problema è detto trattabile se la sua complessità
è polinomiale (se si possono scrivere algoritmi di
complessità polinomiale che lo risolvano)
 Un problema è detto intrattabile se la sua
complessità è esponenziale (se ogni algoritmo che lo
risolve è necessariamente esponenziale)
29
Suddivisione definitiva?
problemi:
non risolubili
intrattabili
trattabili
30
Esistono problemi intrattabili?
 Il problema del fattoriale (esponenziale in spazio)
 Il gioco della torre di hanoi (esponenziale in tempo)
(usato con 64 dischi per rappresentare il tempo
infinito dai monaci buddisti tibetani)
Ci occuperemo d’ora in poi solo della complessità in
tempo.
31
I problemi NP-completi
NP è una classe di problemi tale che:
 Ogni loro soluzione nota consiste di un
algoritmo di complessità esponenziale
 Non è mai stato dimostrato finora che non
possano esistere delle soluzioni polinomiali
32
Perchè “NP-completi”?
P è la classe dei problemi risolubili in tempo polinomiale
(trattabili)
NP è la classe di problemi risolubili in tempo polinomiale
da una macchina con oracolo (oracolo è un oggetto
virtuale in grado di suggerire ad ogni passo la scelta
corretta)
I problemi NP-completi sono nella classe NP e inoltre
hanno soluzioni interdipendenti (cioè una soluzione di
uno di essi si trasforma facilmente nella soluzione di
tutti gli altri)
33
Chi sono?





Il problema del commesso viaggiatore
Il problema dell’orario scolastico
Il problema dello zaino
Il problema della soddisfacibilità logica
………………..
34
P=NP?
Problema aperto
P=NP I problemi che abbiamo elencato sono
trattabili, ma non abbiamo ancora trovato gli
algoritmi migliori per risolverli.
PNP I problemi che abbiamo elencato sono
davvero intrattabili: non è il caso di cercare
ulteriormente.
35
Suddivisione definitiva?
problemi:
non risolubili
intrattabili
PNP
trattabili
P=NP
36
Ma come facciamo?
Obiezione:
I problemi NP-completi si incontrano
quotidianamente, e ci sono soluzioni anche per
dimensioni molto grandi dei dati.
Risposta:
Gli algoritmi usati non risolvono il problema, ma
danno soluzioni parziali di casi particolari: ci
sono scelte (politiche?) del programmatore
dietro ogni soluzione proposta.
37
Il problema della sicurezza delle
comunicazioni
Problema:
Alice e Bob vogliono scambiarsi messaggi in modo che
questi siano “non comprensibili” da terzi.
Soluzione:
Usare due funzioni di codifica e decodifica dei messaggi,
COD e DEC, tali che, se M è un messaggio:
COD(M)=M* (messaggio criptato)
DEC(COD(M))=M (messaggio originale)
COD e DEC sono basate sulla nozione di CHIAVE
38
Esempi di codifica e decodifica
 Chiave: k (numero compreso tra 1 e 21)
COD sostituisce ad ogni lettera del messaggio la
lettera che occorre k posti in avanti nell’alfabeto
(considerato come circolare). DEC fa l’operazione
contraria. (Codice di Cesare)
 Il semplice codice di Cesare può essere complicato
usando scelte diverse di k per lo stesso messaggio,
basate su macchinari rotanti che dopo ogni scelta
guidano alla scelta successiva (codice di Jefferson,
macchina Enigma)
39
Come scambiarsi le chiavi?
Problema:
Prima di iniziare la comunicazione, Alice e Bob devono
essere entrambi a conoscenza delle chiavi su cui sono
basate COD e DEC. Se sono distanti, devono
comunicarsele con un messaggio, ma questo deve
essere a sua volta codificato e quindi…….
regresso infinito!
40
Il sistema a chiave pubblica
(1976, Diffie e Hellman)
Ogni utente del sistema di comunicazione ha una chiave pubblica
(nota a tutti) che viene usata per codificare i messaggi a lui
indirizzati, e una chiave privata che solo lui conosce, che usa per
la decodifica dei messaggi.
Se Bob vuole mandare un messaggio M ad Alice, prende la chiave
pubblica di Alice, CODA, e con questo codifica il messaggio.
Alice, ricevuto il messaggio, userà la sua chiave privata DECA ,
per ottenere:
DECA (CODA (M))=M
41
Non tutto è risolto!
CODA e DECA devono essere l’inversa l’una dell’altra, cioè essere tali
che:
DECA (CODA (M))=M
ma CODA è noto a tutti.
In generale, data una funzione che ha un’inversa, si può calcolare
l’inversa stessa. Ad esempio, se:
CODA (M))=M2
È facilmente indovinabile che:
DECA (M))=
M
42
Il vero problema
Problema 1:
Trovare una funzione COD che sia facilmente calcolabile e che abbia
un’inversa (DEC) ma sia impossibile calcolare DEC a partire da
COD.
Questo problema non è risolubile!
Problema 2:
Trovare una funzione COD che sia facilmente calcolabile e tale che
calcolare la sua inversa sia un problema molto difficile.
In questo modo una spia potrebbe molto difficilmente calcolare
DEC e decodificare il messaggio (ma in linea di principio
potrebbe!)
43
Una soluzione (approssimata)
Formalizziamo meglio il problema
Problema 3:
Trovare una funzione COD tale che calcolare COD sia polinomiale
(trattabile) mentre calcolare la sua inversa sia esponenziale
(intrattabile).
Non si conoscono soluzioni precise di questo problema, ma si può
approssimare nel modo seguente:
COD funzione calcolare la quale sia un problema trattabile
DEC funzione calcolare la quale sia un problema che, anche se non
dimostrato essere intrattabile, possiede per il momento solo soluzioni
esponenziali.
44
Il sistema RSA Ronald Rivest, Adi Shamir e Leonard Adleman
Alice sceglie 2 numeri primi P e Q molto grandi (di circa
200 cifre) e li moltiplica tra di loro. Il numero
risultante PQ ha circa 400 cifre. La chiave pubblica
di Alice è PQ . Per decodificare il messaggio, la
funzione DEC deve conoscere i due fattori P e Q.
Problema della Primalità: trattabile (quindi costruire la
chiave è facile)
Problema della Scomposizione: non si sa, ma si conoscono
solo soluzioni esponenziali (quindi risalire alla
decodifica è difficile).
45
Il sistema è sicuro?
In assoluto no.
Potrebbe sempre accadere che un intruso possa:
1. Indovinare P e Q a partire dal prodotto (Gastone
Paperone)
2. Aver trovato un algoritmo per calcolare P e Q a
partire dal loro prodotto che sia polinomiale, e quindi
veloce (Archimede Pitagorico)
Il sistema è probabilmente sicuro, nel senso che i casi 1 e
2 hanno bassa probabilità di accadere.
46
Morale…..
1.
2.
3.
4.
Il calcolatore non è onnipotente: ci sono problemi che non si
sanno risolvere.
Poiché la maggior parte dei problemi che si incontrano nella vita
quotididiana sono NP-completi, le soluzioni che ci vengono
proposte sono molto spesso parziali e con vincoli aggiuntivi.
Non esistono sistemi assolutamente sicuri, ma solo sistemi
sicuri con una data probabilità.
Se veniamo a sapere che qualcuno ha dimostrato che P=NP
ritiriamo subito tutti i nostri soldi dal conto corrente….
47