Centro Interdipartimentale di Logica e Applicazioni
Dicembre 2003
che catturano
Linguaggi per la descrizione di classi
di complessità computazionale
(orologi, smash, punto e virgola, circoli)
classi di complessità computazionale

modelli di calcolo (macchina di Turing) +
limiti espliciti sulle risorse temporali o spaziali.
 possiamo descrivere le classi con linguaggi,
piuttosto che con modelli di calcolo?
 quali restrizioni dobbiamo imporre ai linguaggi?
 esiste un principio comune a tutte le restrizioni?
1964 - Alan Cobham
The intrinsic computational difficulty of functions
“is it harder to multiply than to add?”
 indipendenza da algoritmo e modello
 analisi metamatematica: proof systems, struttura
delle dimostrazioni e adeguatezza dei sistemi
 analisi metanumerica: sistemi computazionali e
categorie di macchine
 complessità computazionale  classi di funzioni
Ma quale classe di funzioni??
1953 - A. Grzegorczyk
Some classes of recursive functions
… la candidata potrebbe essere la gerarchia di
Grzegorczyk!
E0 = x+y
E1
= x*y
E2 = xy
E0  E1  E2  E3 ...
ottenuta come chisura rispetto a
composizione e ricorsione
limitata
E3 = xx...x (x volte)
E3 = xx...x (xx...x volte)
 Ei = PR
(n) indica il tempo, (n) lo spazio
 fEk
 esiste una TM che calcola f con  in Ek
 esiste una TM che calcola f con  in Ek
f<g (f è “più semplice” di g)  fEk, gEh, con k<h
l’implicazione contraria NON è vera!
… sapere che una funzione è in una classe non è
molto indicativo della sua complessità ...
La prima classificazione di polytime.
0,
ik,
s,
2|x||y|
f(x) = h(g(x), …,g(x))
ricorsione limitata:
indecidibile
f(0,x)=g(x)
f(yi,x)=hi(x,y,f(x,y)) con f(y,x)  k(y,x)
1988 - Harold Simmons
The realm of primitive recursion
“ it is known that many complex constructions
are reducible to primitive recursion. The
question is:
 why is this so?
 there is an illuminating proof of this fact?
 how far can these refinement be pushed and
still remain in the realm of the primitive
recursion?”
1988 - Harold Simmons
The realm of primitive recursion
f(0,x)=g(x)
f(r+1,x)=H(r,x ; f(r,))
a noi interessa il punto e
virgola; divide le variabili in
normal e dormant
è un funzionale; Simmons
trova la (giusta) classe dei
funzionali in cui definire H
una piccola digressione: come si fa l’addizione?
e la moltiplicazione?
(0,x)=x
(y+1,x)=((y,x))+1
(0,a)=0
(b+1,a)=(a,(b,a))
(3,5)=(5,(2,5))
cosa so di questa funzione?
so come calcolarla?
c’è un altro modo per calcolare il prodotto...
(0,x)=x
(y+1,x)=((y,x))+1
(0,a)=0
(b+1,a)=( (b,a),a)
(3,5)=((2,5),5)
quante volte devo applicare il
successore a 5? (2,5) volte!
Sto definendo la funzione prodotto in
termini di se stessa.
predicativo - impredicativo
 la prima definizione di  è predicativa
 la seconda no: definisco  in termini di se stesso
Non ci sorprendiamo del fatto che in Simmons la
prima definizione di  sia legittima, la seconda no.
E osserviamo che NON possiamo definire
l’esponente (x,2)=2x in modo predicativo:
(0,2)=1
(y+1, 2)=((y,2), (y,2))
1992 - Bellantoni & Cook - A new recursion-theoretic
characterization of the polytime functions
Possiamo usare gli strumenti forniti da Simmons
(normal and dormant variables) per caratterizzare
Polytime?
Possiamo fornire una caratterizzazione predicativa,
rinunciando alla ricorsione limitata?
1992 - Bellantoni & Cook - A new recursion-theoretic
characterization of the polytime functions
f(x,… ; y, ...)
normal
0, p,
s(;a), p(;a), if(;a,b,c)
f(0,x ; a) = g(x ; a)
safe
initial functions
safe recursion
f(yi,x ; a) = hi(y,x ; a,f(y,x ; a))
safe composition
f(x ; a) = h(r(x ;) ; t(x ; a))
Polytime = chiusura delle funzioni iniziali sotto
ricorsione e composizione safe, senza input safe.
Riscriviamo somma e prodotto con la safe recursion:
(0 ; x) = x
(y+1 ; x) = s( ; (y ; x))
(0,x ; ) = 0
(y+1,x ; ) = (x ;  (y,x ; ))
Abbiamo una caratterizazione predicativa:
funzioni iniziali + safe rec + safe comp = Polytime.
Cosa succede se violiamo il vincolo di non trasportare
le variabili dalla zona safe a quella unsafe?
iniziali + safe rec + safe comp + k violazioni = Ek
k violazioni  k-ma classe di Grzegorczyk !!
critica a questo approccio ...
... anche se la ricorsione safe riesce a catturare
Polytime, lo fa passando attraverso il modello di
Turing, in modo inefficiente …
...ad esempio,
 semplici ordinamenti (polinomiali) non possono
essere descritti con la ricorsione safe
 semplici funzioni (come il minimo) sono calcolate
con complessità troppo alta.
Martin Hofmann - The strength of non-sizeincreasing computation
insert(x, nil) = cons(x,nil)
insert(x,cons(y,l)) = if x<y then cons(x,cons(y,l))
else cons(x,insert(x,l))
sort(nil) = nil
sort(cons(x,l)) = insert(x,sort(l))
questo algoritmo non è nella forma della safe
recursion.
Loic Colson - Intensional aspects of functional
systems
min(0,y) = 0
il tempo di calcolo
min(s(x),0) = 0
di min è O(min(x,y))
min(s(x),s(y)) = s(min(x,y))
min è ricorsiva primitiva?
min’(x,y) = if(sub(x,y),y,x)
il tempo di calcolo
di min’ è O(y)
O(10,1016) = 1016
O(1016,10) = 10.
Come facciamo a conoscere il più
piccolo fra i due input, se stiamo
ancora definendo min?
1999 - Neil Jones - LOGSPACE and PTIME
characterized by programming languages
“… what is the effect of
the programming style we employ
(functional, imperative, ...) on the
efficiency of the programs
we can possibly write?”
L. Kristiansen & K.H. Niggl - On the computational
complexity of imperative programming languages
un linguaggio che lavora su stack:
pop(X)
push(a,X)
P1;P2
if top(X)a [P]
sequenza
nil(X)
selezione
foreach X [P]
iterazione
tre esempi di stack program (1)
P1  foreach X [foreach X [foreach X [push(a,Y)]]]
se X = v, dopo l’esecuzione di P1 si ha
Y = a|v|3
tre esempi di stack program (2)
P2 
foreach X [nil(Z);
foreach Y [push(a,Z); push(a,Z)];
nil(Y); foreach Z [push(a,Y)]]
se X = v, dopo l’esecuzione di P2 si ha
Z = a2|w|
tre esempi di stack program (3)
P3 
nil(Y); push(a,Y); nil(Z);
foreach X [foreach Y [
push(a,Z); push(a,Z)];push(a,Y)]
se X = v, dopo l’esecuzione di P3 si ha
Z = a|v|2
cosa produce (in P2) la crescita esponenziale?
P2  foreach X [nil(Z);
foreach Y [push(a,Z); push(a,Z)];
nil(Y); foreach Z [push(a,Y)]]
c’è un circolo fra Y e Z;
non accade in P1 o P3.
Diciamo che P2 ha k-measure pari a 1.
… la crescita esponenziale in P2 è dovuta alla
presenza della struttura circolo…
… cosa succede se ci sono due livelli di circoli
annidati?
Diciamo che P2 ha k-measure pari a 2.
abbiamo una misura del livello di annidamento dei
circoli in un programma...
k(pop) = k(push) = k(nil) := 0
k(if top(X)a [P]) = k(P)
k(P1;P2) = max{ k(P1) ; k(P2) }
k(foreach X [P]) = k(P)+1 se in P c’è un circolo
k(foreach X [P]) = k(P)
se non ci sono circoli in P
… con questa misura il cerchio (quello del nostro
ragionamento) si chiude.
 programmi con k-measure pari a n possono
essere simulati da MdT con complessità
temporale in En+2 (la n+2esima classe di
Grzegorczyk)
 MdT con complessità temporale in En+2
possono essere simulate da programmi di
misura n.
… una obiezione sulla natura dei programmi ...
 programmi honestly feasible:
ogni sottoprogramma può essere simulato da una MdT
polinomiale
 programmi dishonestly feasible:
– che calcolano una funzione polinomiale, in tempo più
che polinomiale
– che girano in tempo polinomiale, ma qualche
sottoprogramma, eseguito separatamente, gira in
tempo più che polinomiale.
… ci sono due linee di ricerca:
 restringere il linguaggio degli stack program
(per catturare solo programmi “onesti”)
 migliorare la misura degli stack program (per
catturare il maggior numero possibile di
programmi, anche “disonesti”)
Covino & Pani - A refinement of the k-measure for
stack programs
Fatto: se annidiamo un circolo, la k-measure del
programma cresce.
Domande: cosa succede se...
 annidiamo istruzioni che non modificano lo
spazio complessivo?
 annidiamo sottoprogrammi che non modificano lo
spazio complessivo?
 annidiamo circoli che non modificano lo spazio
complessivo?
Risposta:
 non c’è nessuna crescita nella complessità
della funzione calcolata ...
.
 … ma la k-measure non se ne accorge !
Per riconoscere questa situazione, definiamo una
nuova misura 
distinguiamo i circoli in
 increasing, che fanno aumentare le dimensioni
degli stack coinvolti nel circolo stesso
 not-increasing, che lasciano immutata la
dimensione complessiva dei registri
Se un circolo è not increasing,  non lo considera.
… abbiamo una migliore classificazione dei
programmi (<k per tutti i programmi dishonest ).
 stack program con -measure pari a n
possono essere simulati da MdT con
complessità temporale in En+2 (la n+2esima
classe di Grzegorczyk)
 MdT con complessità temporale in En+2
possono essere simulate da stack program di
misura n.
Buone vacanze !