Efficienza

efficienza: fare le cose con poche risorse

risorse = tempo e spazio

in questo corso vediamo solo il tempo

come misurare il tempo di esecuzione?

cronometriamo il programma?

ma il tempo dipende da:

• computer
• linguaggio di programmazione
• dati
• quanti e quali dati usiamo per provare

cosa misuriamo?

assunzione generale:

non ci interessa il tempo esatto ma una stima generale

indipendente da: computer, linguaggio, dati

in Python…

operazioni semplici e complesse:

semplici

operazioni che coinvolgono singoli dati:
a=2
if b==c+2:, ecc.

complesse

operazioni che richiedono di guardare strutture:
re.search('ab*c|aab*d', 'abbbc')
if x in a:, ecc.

operazioni elementari

ipotesi semplificative:

• le istruzioni su dati scalari (interi, caratteri, ecc.) hanno tutte lo stesso costo
  (es. a=1 ha lo stesso costo di a==b ma anche di a=b*b+c-2/f)
• le istruzioni su strutture complesse si riconducono a istruzioni su scalari

riconducono = ?

operazioni su strutture complesse

il calcolatore in sè non esegue x in a
fa un ciclo sugli elementi, confrontando ogni elemento di a con x

if x in a:
  print 'presente'

c=False
for e in a:
  if x==e:
    c=True
    break
if c:
  print 'presente'

espressioni regolari: ancora più complicato

assunzioni

• solo operazioni semplici
  quelle complesse le trasformiamo
• le operazioni hanno tutte lo stesso tempo di esecuzione

unità di tempo

invece di dire: ogni istruzione 1 millisecondo
o 12 nanosecondi, o 0.9 microsecondi…

una istruzione = tempo 1

non 1 millisecondo, ma una generica unità di tempo

equivale a:

il tempo di esecuzione si misura come numero di istruzioni semplici che vengono eseguite

programmi diversi

occorre fare qualcosa con una lista a

in generale, una stessa cosa si può fare con più programmi diversi

possono avere tempi diversi

per esempio, tre programmi:

1. il primo impiega 5×len(a)
2. il secondo 100×len(a)
3. il terzo 2^len(a)

fanno la stessa cosa, ma con tempi diversi

confronto di tempi

a corta ⇒ tempi brevi comunque

i tempi contano quando a è lunga:

• prog1 e prog2 crescono allo stesso modo
• prog3 cresce molto di più

comportamento asintotico

ci interessa come cresce il tempo quando l'input diventa grande

non ci interessa il tempo preciso

5×len(a) e 100×len(a) crescono in modo simile
2^len(a) molto di più

• prog1 e prog2 li consideriamo efficienti uguali
• prog3 è molto peggio

misura qualitativa

sia n la dimensione dell'input
se è una lista, n=len(a)

esempi di costi:

• 20×n
• 1000×n
• 4×n²
• 2ⁿ

primi due lineari: efficienti
terzo quadratico: un po' meno
quarto esponenziale: non efficiente

c×n, d×n² e f×2ⁿ li consideriamo tempi diversi
ma c×n e d×n no, ecc.

1000×n+2000 è come 2×n+1

notazione O

se:

• n = grandezza dei dati di ingresso
• tempo 45×n² + 1000×n + 500

si dice che il tempo è O(n²)

notazione big-O
O-grande

notazione O: principio

• considerare il tempo in funzione della grandezza dell'ingresso
• prendere la parte che cresce di più
• ignorare costanti moltiplicative

45×n²+1000×n+500 ⇒
45×n² ⇒
   n²

è O(n²)

notazione O: definizione

un programma ha costo (in termini di tempo) O(f(n)) se:

• il suo tempo di esecuzione è t(n)
  dove n è la grandezza dell'input
• esistono due costanti a e b tali che:

  t(n) < a×f(n)+b

notazione O: perchè quella definizione

sull'esempio (si può assumere n≥1):

45×n2+1000×n+500 < 
   45×n2+1000×n2+500 =
   1045×n2+500 =
   a×n2+b

costanti a=1045 e b=500

costo delle istruzioni

con O:

• non conta se un'istruzione impiega tempo 1 o 5
  es. a=2 o a=2*b/4+35-2*c
• conta se impiega tempo proporzionale alla grandezza dell'input
  es. x in a richiede la scansione di a

se poi si misura il tempo in notazione O sono valide le assunzioni fatte sul costo delle singole istruzioni

caso migliore, medio, peggiore

esempio: ricerca in una lista

c=False
for e in a:
  if x==e:
    c=True
    break

caso migliore

x uguale ad a[0]

caso peggiore

x non è nella lista o è alla fine

caso medio

dipende dai valori possibili di x e di a
o meglio: dalle loro probabilità

costo medio

il costo medio dipende dalle probabilità
esempio, x in a:

• x e gli elementi di a sono 0 o 1
  probabilità indipendenti
  caso medio: due passi
• valori interi qualsiasi
  sempre probabilità indipendenti
  caso medio = caso peggiore

caso peggiore

consideriamo i dati sui quali ci vuole più tempo

sulla ricerca in una lista: l'elemento non c'è
oppure è l'ultimo

in altri casi migliore, medio e peggiore coincidono:
esempio: somma degli elementi di una lista

grandezza problemi risolubili

altro modo di vedere l'efficienza:

grandezza dell'input che un programma può risolvere in un dato tempo

grandezza massima dell'input

più grande problema risolubile in un certo tempo
assumendo una operazione ogni millesimo di secondo

grandezza massima dell'input: commenti

all'inizio numeri simili

problema grande 200:

• il primo ce la fa in meno di un minuto
• al secondo serve più di un minuto
• al terzo più di un'ora
• il quarto nemmeno in un giorno intero

costi di esecuzione: nomi

grandezza dell'input: n

costo lineare

O(n): esempio 100×n+2010

costo quadratico

O(n²): esempio 10×n²+500×n+9

costo cubico

O(n³)

costo esponenziale

O(2ⁿ)

in generale:

costo O(n^c) = costo polinomiale

valutazione qualitativa dei costi

• polinomiale è meglio di esponenziale
• se polinomiale, è meglio un grado basso
  es. O(n²) è meglio di O(n³)

istruzione dominante

intuitivamente:

è una qualsiasi delle istruzioni che vengono eseguite più volte

sono quelle dei cicli "più interni"

esempio…

istruzione dominante: esempio

a = [3, 2, -1, 2, 1]

s = 0
for x in a:
  s = s + x

print(s)

somma di una lista

numero di esecuzioni

a = [3, 2, -1, 2, 1]

s = 0
for x in a:
  s = s + x

print(s)

1

1

5

1

istruzione eseguita più volte: s = s + x
è l'istruzione dominante di questo programma

è quella dentro il ciclo

input generico

non siamo interessati al tempo di esecuzione con input specifico

vogliamo sapere quanto cresce il tempo quando cresce l'input

⇒ valutazione con lista di lunghezza arbitraria

costo, con lista generica

s = 0
for x in a:
  s = s + x

print(s)

1

n

1

lista a lunga n

costo complessivo

s = 0
for x in a:
  s = s + x

print(s)

1

n

1

costo 1 + n + 1

O(n)

istruzione dominante e notazione O

lista lunga n:

• l'istruzione dominante s = s + x viene eseguita n volte
• il costo è O(n)

costo asintotico = numero esecuzioni dell'istruzione dominante

come individuare l'istruzione dominante

s = 0
for x in a:
  s = s + x

print(s)

1

n

1

istruzione nel ciclo

eseguita n volte
dominante

istruzioni fuori dal ciclo

eseguite 1 volta
non dominante

l'istruzione dominante è quella nel ciclo

variante: somma di prodotti

sommare i valori a[0] × … × a[i]
per tutti gli indici i

somma di prodotti: programma

a = [3, 2, -1, 2, 1]

s = 0
for i,x in enumerate(a):
  p = 1
  for y in a[0:i+1]:
    p = p * y
  s = s + p

print(s)

per ogni elemento della lista
calcola il prodotto
li somma

somma di prodotti: costi

s = 0
for i,x in enumerate(a):
  p = 1
  for y in a[0:i+1]:
    p = p * y
  s = s + p

print(s)

1

n

???
n

1

quante volte viene eseguito p = p * y?

somma di prodotti: ciclo interno

s = 0
for i,x in enumerate(a):
  p = 1
  for y in a[0:i+1]:
    p = p * y
  s = s + p

print(s)

1

n

???
n

1

l'intero ciclo interno for y... viene eseguito n volte

l'istruzione p = p * y viene eseguita i volte
ogni volta che si esegue il ciclo interno for y...

somma di prodotti: costo istruzioni

s = 0
for i,x in enumerate(a):
  p = 1
  for y in a[0:i+1]:
    p = p * y
  s = s + p

print(s)

1

n

n × (i + 1)
n

1

quanto vale n × (i + 1)?

i + 1 va da 1 a n
approssimato: n/2

somma di prodotti: costo totale

s = 0
for i,x in enumerate(a):
  p = 1
  for y in a[0:i+1]:
    p = p * y
  s = s + p

print(s)

1

n

n × n / 2
n

1

costo totale:

  1 + n + n×n/2 + n + 1 =
  n×n / 2 + 2×n + 2 =
  n2/2 + 2×n + 2
  O(n2)

somma di prodotti: istruzione dominante

s = 0
for i,x in enumerate(a):
  p = 1
  for y in a[0:i+1]:
    p = p * y
  s = s + p

print(s)

1

n

n × n / 2
n

1

istruzione eseguita più volte: p = p * y

è quella nel ciclo interno

somma di prodotti: istruzione dominante e costo totale

s = 0
for i,x in enumerate(a):
  p = 1
  for y in a[0:i+1]:
    p = p * y
  s = s + p

print(s)

1

n

n × n / 2
n

1

istruzione dominante

eseguita n × n / 2 volte

costo totale

O(n²)

costo totale = numero di esecuzioni dell'istruzione dominante

istruzione dominante: in concreto

si guardano le istruzioni dentro i cicli più interni

si vede quante volte vengono eseguite
sempre in funzione della grandezza dell'input

questo dice il costo del programma in notazione O-grande

somma di prodotti: osservazione

s = 0
for i,x in enumerate(a):
  p = 1
  for y in a[0:i+1]:
    p = p * y
  s = s + p

print(s)

passo i

calcola p = a[0] × … × a[i]

passo i + 1

calcola p = a[0] × … × a[i] × a[i+1]
uguale a p = (a[0] × … × a[i]) × a[i+1]

parte fra parentesi: valore di p al passo precedente

somma di prodotti: miglioramento

s = 0
p = 1
for i,x in enumerate(a):
  p = p * x
  s = s + p

print(s)

invece di p = (a[0] × … × a[i]) × a[i+1]

si calcola p = (p) × a[i+1]

valore precedente di p

somma di prodotti: costo del miglioramento

s = 0
p = 1
for i,x in enumerate(a):
  p = p * x
  s = s + p

print(s)

1


n
n

1

costo totale:

1 + n + n + 1 =
2 × n + 2
O(n)

osservazione

stesso problema

due programmi:

• il primo ha costo O(n²)
• il secondo ha costo O(n)

il primo programma è una soluzione più veloce dello stesso problema

problemi e programmi

uno stesso problema si può risolvere con più programmi

alcuni possono essere più veloci di altri, per es:

• per un problema esiste un programma quadratico O(n²) e uno lineare O(n)
• per un altro problema esiste un programma esponenziale O(2ⁿ) e uno cubico O(n³)

si sceglie il programma più veloce

costo e complessità

programma

costo
(= quante istruzioni vengono eseguite)

problema

complessità
(= costo del suo programma migliore)

complessità di un problema

• si considera il programma migliore che risolve il problema
• si fa una distinzione solo fra polinomiale ed esponenziale

P = insieme dei problemi che si risolvono in tempo polinomiale

problemi in P

• vedere se un elemento è in una lista
• decidere il valore di una formula booleana dati i valori delle variabili
• sommare due numeri interi in precisione arbitraria
• …

consideriamo sempre costo al crescere dell'input
non ha senso valutare il costo di una somma a 64 bit

problemi non in P

• tutti quelli indecidibili (ovviamente)
• decidere se il primo giocatore ha una strategia vincente nel gioco dei ciottoli
• forse: decidere se una formula booeana è vera per qualche valore della variabili (SAT)
• forse: trovare una copertura di un grafo
• forse: decidere se un sottoinsieme di un insieme di interi ha somma k data
• …

forse?

tre casi possibili:

si conosce un programma che impiega tempo polinomiale per un problema

problema in P

si dimostra che non esiste un programma che impiega tempo polinomiale per un problema

problema non in P

non si conosceono programmi che impiegano tempo polinomiale per un problema
ma nemmeno è stato dimostrato che non esistono

non si sa se il problema è in P o meno

esempio di problema in "forse"

subset-sum:

dato:

insieme di interi e un numero

soluzione:

sottoinsieme la cui somma è uguale al numero

soluzioni per casi specifici

numero 11, insieme di interi {3, 6, 1, 4, 2},

soluzione {3, 6, 2}
la somma è 11

numero 1, insieme di interi {7, 9, 3, -2, 5, -10, 4},

soluzione {7, -10, 4}, la somma è 1

numero 10, insieme di interi {5, 9, -3, -5, 11, 3},

nessuna soluzione

numero 10, insieme di interi {3, 4, 11, 2}}

nessuna soluzione

soluzione facile

itertools.combination(insieme, n)

tutti i sottoinsiemi di n elementi dell'insieme

ciclo da 0 a len(insieme):
tutti i sottoinsiemi

per ognuno si calcola la somma

soluzione facile: verifica della soluzione

def verificasomma(numero, insieme):
    s = 0
    for e in insieme:
        s = s + e
    return s == numero

subsetsum.py

costo: O(n)

soluzione facile: ciclo sui sottoinsiemi

import itertools

…

def subsetsum(numero, insieme):
    for i in range(0, len(insieme)):
        for s in itertools.combinations(insieme, i):
            if verificasomma(numero, s):
                return s
    return None

subsetsum.py

soluzione facile: programma completo

import itertools

def verificasomma(numero, insieme):
    s = 0
    for e in insieme:
        s = s + e
    return s == numero

def subsetsum(numero, insieme):
    for i in range(0, len(insieme)):
        for s in itertools.combinations(insieme, i):
            if verificasomma(numero, s):
                return s
    return None

print(subsetsum(11, {3, 6, 1, 4, 2}))
print(subsetsum(1,  {7, 9, 3, -2, 5, -10, 4}))
print(subsetsum(10, {5, 9, -3, -5, 11, 3}))
print(subsetsum(10, {3, 4, 11, 2}))

subsetsum.py

costo?

soluzione facile: costo complessivo

def subsetsum(numero, insieme):
    for i in range(0, len(insieme)):
        for s in itertools.combinations(insieme, i):
            if verificasomma(numero, s):
                return s
    return None

insieme di grandezza n

ciclo esterno: eseguito n volte

ciclo interno: eseguito una volta per ogni sottoinsieme

numero totale di sottoinsiemi: esponenziale in n

costo O(2ⁿ)

schema di soluzione facile

for i in range(0, len(insieme)):
    for s in itertools.combinations(insieme, i):
        if verificasomma(numero, s):
            return s
return None

 
per ogni sottoinsieme:
    se la verifica è positiva:
        ritorna il sottinsieme
ritorna che non ci sono soluzioni

altri problemi con cui funziona?

soluzione facile per altri problemi

somma di sottoinsiemi

per ogni sottoinsieme:
    se la verifica è positiva:
        ritorna il sottinsieme
ritorna che non ci sono soluzioni

formula soddisfacibile

per ogni sottoinsieme di variabili:
    se il modello in cui sono vere quelle false le altre soddisfa la formula:
        ritorna il modello
ritorna che non ci sono modelli

copertura di un grafo

per ogni sottoinsieme di nodi di un grafo:
    se è una coperatura del grafo della grandezza data:
        ritorna il sottoinsieme
ritorna che non ci sono coperture

percorso in un grafo

per ogni sequenza di nodi di un grafo:
    se è un percorso nel grafo fra i due nodi dati:
        ritorna la sequenza
ritorna che non ci sono percorsi

ordine topologico in un grafo

per ogni sequenza di nodi di un grafo:
    se è un ordine topologico nel grafo:
        ritorna la sequenza
ritorna che non ci sono ordini topologici

sequenze: itertools.permutations(insieme, numero)
sempre numero esponenziale

NP

problemi che si possono risolvere con un ciclo su itertools.combinations() o itertools.permutations() e …

manca una precisazione

NP: la verifica

problemi che si possono risolvere con un ciclo su itertools.combinations() o itertools.permutations() con verifica in P

• ciclo sui sottoinsiemi o le permutazioni
• verifica impiega tempo polinomiale

somma dispari

dato:

insieme di interi e un numero

soluzione:

sottoinsieme la cui somma è dispari

somma dispari: soluzione con itertools

for i in range(0, len(insieme)):
    for s in itertools.combinations(insieme, i):
        if verificasommadispari(s):
            return set(s)

problema in NP

subsetodd.py

somma dispari: soluzione diretta

for e in insieme:
    if e % 2 == 1:
         return {e}
return None

operazione dominante: e % 2 == 1

eseguita len(insieme) volte:
n = len(insieme)

problema in P

subsetodd.py

perchè la soluzione veloce funziona

for e in insieme:
    if e % 2 == 1:
         return {e}
return None

l'insieme contiene un numero dispari

la somma dell'insieme che contiene solo quel numero è dispari

l'insieme contiene solo numeri pari

la somma di numeri pari è sempre pari

operazioni: numero di elementi nell'insieme

somma dispari è sia in P che in NP

ha una soluzione con itertools

⇒ è in NP

ha una soluzione O(n)

⇒ è in P

vale per tutti?

P è contenuto in NP

problema in P ⇒ anche in NP

esempio con input un insieme:

    for i in range(0, len(insieme)):
        for s in itertools.combinations(insieme, i):
            if soluzionepolinomiale(s):
                return s

NP, graficamente

problemi con soluzione "ciclo itertools + verifica in P"

copertura di un grafo, sottoinsieme con somma dispari, soddisfacibilità proposizionale, ordine topologico, somma di un sottoinsieme

P, graficamente

alcuni problemi hanno anche un programma che gira in tempo polinomiale

sottoinsieme con somma dispari, ordine topologico

altri problemi

dove sono copertura di un grafo, soddisfacibilità proposizionale, somma di un sottoinsieme?

sono in NP perchè hanno la soluzione itertools+verifica

non si conoscono programmi polinomiali
sono fuori da P?

programmi non noti

copertura di un grafo, soddisfacibilità proposizionale, somma di un sottoinsieme

non si conoscono programmi polinomiali

• potrebbero esistere
• potrebbero non esistere

potrebbero essere in P oppure no

esempio: sat

non si conoscono algoritmi polinomiali

potrebbero esistere

potrebbe essere in P
oppure no

riduzione verso sat

programma polinomiale che converte:

un numero e un insieme di interi
⇓
una formula proposizionale

tale che:

esiste un sottoinsieme di interi con somma quel numero

⇒ la formula è soddisfacibile

non esiste un sottoinsieme di interi con somma quel numero

⇒ la formula non è soddisfacibile

a cosa serve?

programmi polinomiali

se sat ha un programma polinomiale
ce l'ha anche somma:

• converte numero e insiemi in una formula (polinomiale)
• verifica se ha un modello (polinomiale)

somma di due polinomi: polinomio

se sat è in P, lo è anche somma

riduzioni da tutti i problemi in NP

teorema di Cook (1971): tutti i problemi in NP si riducono a sat

se sat è in P
tutti i problemi in NP sono anche in P

tutti i problemi in P?

se sat è in P
tutti i problemi in NP sono anche in P

altri programmi polinomiali per questi problemi non sono mai stati trovati
ritenuto sempre meno probabile che esistano per tutti

problema simile: somma

in NP
non si sa se è in P

servono tutte le riduzioni?

unica riduzione

non servono tutte le riduzioni

basta quella da sat

doppio passo

esiste una riduzione da sat a somma
⇓
ogni altro problema in NP si riduce a somma

• altro problema ⇒ sat
• sat ⇒ somma
• programma polinomiale per somma

NP-hard

NP-hard: problemi a cui si riducono tutti gli altri in NP

anche uno solo è in P
⇓
tutti in P

ritenuto improbabile

teorema di Cook

teorema di Cook (1971): tutti i problemi in NP si riducono a sat

dimostrato attraverso macchine di Turing

definizione di NP

semplificata

programma itertools + verifica polinomiale

esatta

problemi risolubili da una macchina di Turing non derministica che impiega tempo polinomiale

programmi e macchine di Turing

macchina di Turing = programma

esiste programma = esiste macchina di Turing

nondeterminismo e itertools

primo passo, non deterministico:
scrive 0 e 1

nastro a destra

secondo passo

secondo passo, non deterministico:
scrive 0 e 1
non importa cosa è stato scritto prima

nastro a destra

dopo n passi

sono stati scritti n bit

tutte le combinazioni possibili

dopo n passi

sottoinsieme di un insieme di n elementi
⇅
sequenza di n bit

primo bit dice se il primo elemento dell'insieme è nel sottoinsieme
il secondo bit lo dice per il secondo elemento
…

verifica

primi n passi:
generati tutti i sottoinsiemi
tempo n

verifica: polinomiale

macchina di Turing non derministica
tempo n + polinomiale = polinomale

problemi in NP

macchina di Turing non deterministica, tempo polinomiale
= esiste un sottoinsieme che soddisfa una verifica polinomiale

NP sono tutti i problemi di questo tipo

NP = esiste qualcosa che rende vero qualcosa

altri problemi in NP \ P

imsat: restrizione di sat a certe formule

è in NP
non si sa se è in P
non si sa se è NP-hard

teorema di Ladner:
esistono problemi in NP che non sono in P e non sono NP-hard
se NP non è uguale a P

ciclo + verifica: generalizzazione

NP = ciclo + verifica in P

se la verifica non è in P?
se è in NP?

ciclo + verifica in NP

NP:

ciclo + verifica in P

NP^NP:

ciclo + verifica in NP

per precisione:
il contrario della verifica in NP

esempio di problema in NP^NP

∃∀QBF

dato: formula ∃X ∀ Y . F
dove F è una formula proposizionale

risultato: esiste una valutazione di X tale che per ogni valutazione di Y la formula F è vera?

NP-hardness

∃ X ∀ Y . F con Y=\emptyset è ∃ X . F

∃∀QBF include sat come sottoproblema

∃∀QBF è NP-hard

non è in NP (forse)

gerarchia polinomiale

ciclo + verifica in NP^NP, ecc.

∃∀∃….F

numero qualsiasi di quantificatori

problemi non in P

esistono problemi che sicuramente non sono in P

esempio: problema dei ciottoli

il gioco dei ciottoli

esempio di schema:

(X)------+
 |       |
 |       |
 |%------|--------(X)
 |       |       / |
 |       |     /   |
 |       |    |    |%----------+
 |       |    |    |           |
 V       %    |    V           |
( )-----------|->(( ))        ( )
 |            |                ^
 |            %                |
 +-----------------------------+

la disposizione (linee, cerchi, ecc,) può variare

spostamento dei ciottoli

(X) -----------> ( )
         %
         |
         |
        (X)

( ) -----------> (X)
         %
         |
         |
        (X)

possibile solo se il cerchio sotto è occupato

gioco

• a turno i due giocatori muovono un ciottolo
• se uno dei giocatori non può muovere, l'altro ha vinto
• chi riesce a portare un ciottolo nel doppio cerchio ha vinto

i ciottoli non sono di nessuno
tutti e due i giocatori li possono muovere

problema

il primo giocatore ha una strategia vincente?

= riesce a muovere in modo tale da vincere sempre?

strategia: esempio (1)

 +------------------>( )
 |       %           | |
 |       |           | |
 |       |           % |
(X)     (X)------------|---->(( ))
 |       |             |       ^
 |       |             |       |
 |       %             %       |
 +------------>( ) ------------+

un esempio di disposizione iniziale

strategia: esempio (2)

 +------------------>(X)
 |       %           | |
 |       |           | |
 |       |           % |
( )     (X)------------|---->(( ))
 |       |             |       ^
 |       |             |       |
 |       %             %       |
 +------------>( ) ------------+

una possibile mossa del primo giocatore:
spostare il primo ciottolo in alto

ma…

strategia: esempio (3)

 +------------------>(X)
 |       %           | |
 |       |           | |
 |       |           % |
( )     ( )------------|---->((X))
 |       |             |       ^
 |       |             |       |
 |       %             %       |
 +------------>( ) ------------+

tocca al secondo giocatore

sposta l'altro ciottolo nel nodo finale ⇒ vince

strategia: esempio (4)

 +------------------>( )
 |       %           | |
 |       |           | |
 |       |           % |
(X)     (X)------------|---->(( ))
 |       |             |       ^
 |       |             |       |
 |       %             %       |
 +------------>( ) ------------+

torniamo all'inizio

strategia: esempio (5)

 +------------------>( )
 |       %           | |
 |       |           | |
 |       |           % |
( )     (X)------------|---->(( ))
 |       |             |       ^
 |       |             |       |
 |       %             %       |
 +------------>(X) ------------+

se il primo giocatore sposta il primo ciottolo in basso…

strategia: esempio (6)

 +------------------>( )
 |       %           | |
 |       |           | |
 |       |           % |
( )     (X)------------|---->(( ))
 |       |             |       ^
 |       |             |       |
 |       %             %       |
 +------------>(X) ------------+

il secondo giocatore non può muovere

il primo ha vinto

problema della strategia

dati:

• una disposizione di linee e cerchi
• le posizioni iniziali dei ciottoli

il problema è: esiste una strategia che consente al primo giocatore di vincere sempre?

complessità del problema dei ciottoli

si può dimostrare che:

ogni programma per verificare se esiste una strategia vincente per il problema dei ciottoli impiega tempo esponenziale

altri problemi hanno questa caratteristica

problemi esponenziali

complessità esponenziale = il migliore programma che li risolve impiega tempo esponenziale nella dimensione dell'input

esempio: strategia vincente nel gioco dei ciottoli

diversi problemi hanno complessità esponenziale

NP=P? NP=EXPTIME?

EXPTIME = problemi risolubili in tempo esponenziale

P ⊂ EXPTIME

P ⊆ NP ⊆ EXPTIME

potrebbe essere P=NP

collocazione di NP: conseguenze

NP=P

anche i problemi più difficili in NP (es: sat) si risolvono in tempo polinomiale

NP=EXPTIME

i problemi più difficili di NP richiedono tempo esponenziale

molti ritengono che NP≠P

premio di $1000000 per chi risolve la questione