Fondamenti Logici dell’Informatica

(1)

Fondamenti Logici dell’Informatica

Corso di Laurea Magistrale in Informatica Logica e Complessità

Ugo Dal Lago

Anno Accademico 2018-2019

(2)

La Complessità Computazionale

I Uno degli scopi più importanti che l’informatica teorica is prefigge è la classificazione dei problemi computazionali rispetto alla quantità di risorse che la loro risoluzione richiede.

I In questo modo, è possibile comprendere l’intrinseca difficoltà dei problemi computazionali che ci troviamo a risolvere.

I Parimenti, si può in questo modo studiare quali siano i limiti del calcolo con risorse limitate.

I Per fare tutto questo, occorre però capire come formalizzare i concetti di:

I Problema Computazionale;

I Algoritmo;

I Risorse e limiti al loro uso.

I La teoria che ne risulta è nient’altro che la complessità computazionale.

(3)

La Complessità Computazionale

I Algoritmo;

(4)

La Complessità Computazionale

I Algoritmo;

(5)

La Complessità Computazionale

I Algoritmo;

(6)

La Complessità Computazionale

I Algoritmo;

(7)

Problema Computazionale

I Tradizionalmente, i problemi di cui si occupa la complessità computazionale sono il calcolo di funzioni nella forma f : B → B dove B = {0, 1}^∗ è l’insieme di tutte le stringhe binarie.

I Perché?

B f B

Grafi Alberi Stringhe

.. .

Grafi Alberi Stringhe

.. .

I Spesso, ci si concentra sui problemi decisionali, cioè quelli in cui f (B) ⊆ {0, 1}.

I Tali problemi sono in corrispondenza biunivoca con i sottoinsiemi di B.

(8)

Problema Computazionale

I Perché?

B f B

Grafi Alberi Stringhe

.. .

Grafi Alberi Stringhe

.. .

(9)

Problema Computazionale

I Perché?

B f B

Grafi Alberi Stringhe

.. .

Grafi Alberi Stringhe

.. .

(10)

Problema Computazionale

I Perché?

B f B

Grafi Alberi Stringhe

.. .

Grafi Alberi Stringhe

.. .

(11)

Problema Computazionale

I Perché?

B f B

Grafi Alberi Stringhe

.. .

Grafi Alberi Stringhe

.. .

(12)

Dai Problemi agli Algoritmi

I Le funzioni incapsulano conoscenza dichiarativa e non imperativa

I Se f : B → B, allora f ⊆ B × B.

I Occorre cambiare punto di vista.

f (x) x f

I(x) · · · F (x)

I La relazione −→ non deve dipendere da x, e ogni passo^A deve essere elementare.

I In tal caso A calcola f e scriviamoJAK = f .

I Agli algoritmi può essere data natura formale in tanti modi diversi.

I Macchine di Turing.

I Random Access Machines.

I . . .

(13)

Dai Problemi agli Algoritmi

f (x) x f

I(x) · · · F (x)

I . . .

(14)

Dai Problemi agli Algoritmi

f (x) x f

I(x) · · · F (x)

I . . .

(15)

Dai Problemi agli Algoritmi

f (x) x f

I(x) · · · F (x)

I . . .

(16)

Dai Problemi agli Algoritmi

f (x) x f

I(x)

^A

· · ·

^A

F (x)

I . . .

(17)

Dai Problemi agli Algoritmi

f (x) x f

I(x)

^A

· · ·

^A

F (x)

I . . .

(18)

Dai Problemi agli Algoritmi

f (x) x f

I(x)

^A

· · ·

^A

F (x)

I . . .

(19)

Misurare l’Uso delle Risorse

I Quali potrebbero essere le risorse di calcolo d’interesse?

I Tempo.

I Il tempo è modellato come il numero di transizioni necessarie ad arrivare a F (x) partendo da I(x).

I Certamente in questo modo otteniamo un’idealizzazione del vero tempo di calcolo, il quale ovviamente dipende dalla complessità di ogni singolo passo di calcolo.

I Il tempo che l’algoritmo A impiega sull’input x è indicato con TIME_A(x)

I Spazio.

I Lo spazio di calcolo è invece modellato come la massima lunghezza dei risultati intermedi necessari ad ottenre F (x) a partire da I(x).

I Non si tiene conto né dello spazio necessario a tener traccia di x, né di quello necessario a tener traccia di f (x).

I Il tempo che l’algoritmo A impiega sull’input x è indicato con SPACEA(x)

I La lunghezza di una stringa x è indicata con |x|.

(20)

Misurare l’Uso delle Risorse

I Tempo.

I Spazio.

(21)

Misurare l’Uso delle Risorse

I Tempo.

I Spazio.

(22)

Misurare l’Uso delle Risorse

I Tempo.

I Spazio.

(23)

Classi di Complessità

I Possiamo prima di tutto definire delle classi concrete, parametriche su una funzione g : N → N.

DTIME (g) = {L ⊆ B | ∃A.JAK = L ∧ ∀x.TIMEA(x) ≤ g(|x|)};

DSPACE (g) = {L ⊆ B | ∃A.JAK = L ∧ ∀x.SPACEA(x) ≤ g(|x|)}.

I Possiamo poi definire vere e proprie classi di complessità, che permettono una classificazione dei problemi più

informativa:

P = [

g∈POLY

DTIME (g) PSPACE = [

g∈POLY

DSPACE (g)

L = [

g∈LOGA

DSPACE (g)

dove POLY è la classe dei polinomi e LOGA è la classe delle funzioni logaritmiche.

(24)

Nondeterminismo

I Se il problema computazionale è decisionale, ha senso pensare ad algoritmi che non siano deterministici.

I Per esempio, potremmo avere un comportamento puramente nondeterministico.

f (x) x f

I(x)

F

₁

(x) A

F

_n

(x)

.. .

f (x) = 1 se e solo se esiste i con F

_i

(x) ` e finale.

I In tal caso A decide f e scriviamo JAK = f .

I Si possono definire poi NDTIME (g) e NP, seguendo lo stesso schema visto precedentemente per gli algoritmi deterministici.

(25)

Nondeterminismo

f (x) x f

I(x)

F

₁

(x) A

F

_n

(x)

.. .

f (x) = 1 se e solo se esiste i con F

_i

(x) ` e finale.

(26)

Nondeterminismo

f (x) x f

I(x)

F

₁

(x) A

F

_n

(x)

. ..

f (x) = 1 se e solo se esiste i con F

_i

(x) ` e finale.

(27)

Nondeterminismo

f (x) x f

I(x)

F

₁

(x) A

F

_n

(x)

. ..

f (x) = 1 se e solo se esiste i con F

_i

(x) ` e finale.

(28)

Nondeterminismo

f (x) x f

I(x)

F

₁

(x) A

F

_n

(x)

. ..

f (x) = 1 se e solo se esiste i con F

_i

(x) ` e finale.

(29)

Nondeterminismo

f (x) x f

I(x)

F

₁

(x) A

F

_n

(x)

. ..

f (x) = 1 se e solo se esiste i dove F

_i

(x) ` e finale.

(30)

Nondeterminismo

f (x) x f

I(x)

F

₁

(x) A

F

_n

(x)

. ..

f (x) = 1 se e solo se esiste i dove F

_i

(x) ` e finale.

(31)

Nondeterminismo

f (x) x f

I(x)

F

₁

(x) A

F

_n

(x)

. ..

f (x) = 1 se e solo se esiste i dove F

_i

(x) ` e finale.

(32)

Una Teoria Giovane

I Con tecniche abbastanza semplici si riesce a dimostrare che L ⊆ P ⊆ NP ⊆ PSPACE.

I Con tecniche altrettanto semplici, si può concludere che L ( PSPACE.

I A tutt’oggi, non è però chiaro quali tra le tre inclusioni di cui sopra siano strette. Almeno una deve essere stretta, ma potrebbero anche essere tutte strette.

I Più di quarant’anni di sforzi non hanno portato ad alcun decisivo progresso nella risoluzione di questo problema.

I La comunità scientifica è convinta che servano tecniche diverse da quelle puramente combinatoriche.

(33)

Una Teoria Giovane

(34)

Una Teoria Giovane

(35)

Una Teoria Giovane

(36)

Una Teoria Giovane

(37)

Grafi Come Strutture

I La logica predicativa offre un modo di parlare di insiemi di oggetti, ovvero di linguaggi.

I Supponiamo di utilizzare un vocabolario costituito dal simbolo binario di uguaglianza = e da un simbolo binario E.

I Consideriamo poi la seguente formula:

BIN ≡ ∀x.∃y.∃z.∀w.(y 6= z ∧ E(x, y) ∧ E(x, z))

∧ (E(x, w) → w = y ∨ w = z).

I Consideriamo universi finiti nella forma A_n= {1, . . . , n}. Un’interpretazione I per tale universo consta,

fondamentalmente, di una relazione binaria E_I su A_n.

I L’uguaglianza è sempre interpretata con la relazione identica.

I (A_n, I) è un grafo.

I Ogni formula nel vocabolario costituito da E e dall’uguaglianza può quindi essere vista come un riconoscitore di grafi.

(38)

Grafi Come Strutture

∧ (E(x, w) → w = y ∨ w = z).

(39)

Grafi Come Strutture

∧ (E(x, w) → w = y ∨ w = z).

(40)

Grafi Come Strutture

∧ (E(x, w) → w = y ∨ w = z).

I Consideriamo universi finiti nella forma A_n= {1, . . . , n}.

Un’interpretazione I per tale universo consta,

(41)

Grafi Come Strutture

∧ (E(x, w) → w = y ∨ w = z).

I Consideriamo universi finiti nella forma A_n= {1, . . . , n}.

Un’interpretazione I per tale universo consta,

(42)

Complessità Descrittiva

Formule Logiche Linguaggi

Interpretazioni Stringhe

I Esistono logiche che catturano, che caratterizzano, classi di complessità importanti come P o NP?

I È possibile capire qualcosa di profondo circa le classi di complessità indagandone la natura logica?

I Il resto di questa parte del Corso sarà dedicato a dare una risposta alla prima di queste domande.

(43)

Complessità Descrittiva

Formule Logiche Linguaggi

Interpretazioni Stringhe

(44)

Complessità Descrittiva

Formule Logiche Linguaggi

Interpretazioni Stringhe

(45)

Interpretazioni come Stringhe

I Per dare concretezza alla complessità descrittiva, occorre prima di tutto capire come le interpretazioni possano essere descritte in modo compatto.

I Supponiamo di lavorare con l’universo finito A_n= {1, . . . , n}.

I Supponiamo che un vocabolario sia costituito da m simboli predicativi P₁, . . . , Pm e da k simboli di funzione f₁, . . . , fk, tutti di arietà 0.

I Una qualunque interpretazione I per tale vocabolario può essere quindi descritta da una stringa binⁿ(I) ∈ B dove

binⁿ(I) = binⁿ(P₁) . . . binⁿ(P_n)binⁿ(f₁) . . . binⁿ(f_k) e:

I Per ogni 1 ≤ i ≤ m, la stringa binⁿ(P_i) ha lunghezza pari a n^ar(Pⁱ⁾, dove ar(P_i) è l’arietà di P_i. Tale stringa specifica quando ogni possibile tupla fa parte di (P_i)_I oppure no.

I Per ogni 1 ≤ i ≤ k, la stringa binⁿ(f_i) ha lunghezza pari a dlog₂(n)e e specifica quale elemento di An interpreta fi.

(46)

Interpretazioni come Stringhe

(47)

Interpretazioni come Stringhe

(48)

Interpretazioni come Stringhe

I Per ogni 1 ≤ i ≤ k, la stringa binⁿ(f_i) ha lunghezza pari a dlog₂(n)e e specifica quale elemento di A_n interpreta f_i.

(49)

Formule come Funzioni

I Una formula predicativa F si dice chiusa quando nessuna variabile occorre libera in F .

I Ad ogni formula predicativa chiusa F si può far corrispondere un sottoinsieme struct(F ) come segue:

struct(F ) = {binⁿ(I) | (An, I) |= F } ⊆ B.

I A questo punto ci si può chiedere quale sia la classe di linguaggi che una certa logica caratterizza.

I Nel caso della logica predicativa abbiamo per esempio FO = {struct(F ) | F è una formula predicativa chiusa}

(50)

La Logica Predicativa è Interessante?

I Una domanda a questo punto molto interessante è la seguente: FO coincide con una classe interessante?

I Per fare in modo che la logica predicativa abbia un minimo di potere espressivo, occorre assumere che il vocabolario includa:

I Tre simboli funzionali di arietà nulla chiamati 0,1, max , interpretati nel modo ovvio.

I Due simboli predicativi binari ≤ e BIT , anch’essi interpretati nel modo ovvio.

Lemma FO ⊆ L. Lemma

PARITY /∈ FO. Teorema FO ( L.

(51)

La Logica Predicativa è Interessante?

Lemma FO ⊆ L. Lemma

PARITY /∈ FO. Teorema FO ( L.

(52)

La Logica Predicativa è Interessante?

Lemma FO ⊆ L.

Lemma

PARITY /∈ FO.

Teorema FO ( L.

(53)

Logica Predicativa del Secondo Ordine

I Conviene a questo punto cercare una logica più espressiva.

I Una scelta naturale è quella di considerare un’estensione delle formule con variabili al second’ordine, che indicano una qualunque relazione, anziché un oggetto:

F ::= . . .

|

Xⁿ(t1, . . . , tn)

|

∃Xⁿ.F

|

∀Xⁿ.F.

I La semantica di queste formule segue quella della logica predicativa, ma occorre che ξ assegni una relazione n-aria ad ogni variabile Xⁿ.

I In questo modo:

(A, I), ξ |= Xⁿ(t1, . . . , tn) sse (Jt¹K

(A,I)

ξ , . . . ,JtⁿK

(A,I)

ξ ) ∈ ξ(Xⁿ) (A, I), ξ |= ∃Xⁿ.F sse (A, I), ξ[Xⁿ:= R] |= F

per qualche R ⊆ Aⁿ (A, I), ξ |= ∀Xⁿ.F sse (A, I), ξ[Xⁿ:= R] |= F

per tutte le R ⊆ Aⁿ ..

.

(54)

Il Teorema di Fagin

I La logica al second’ordine è troppo potente per i nostri scopi.

I Ne esiste però un frammento molto interessante, che chiamiamo logica al second’ordine esistenziale, le cui formule sono le formule che possono essere scritte nella forma

∃Xⁿ¹. . . . ∃Xⁿ^m.F

dove F è una formula predicativa al prim’ordine.

I A questo punto è facile generalizzare quanto visto in precedenza per la logica predicativa:

∃SO = {struct(F ) | F è una formula

al second’ordine esistenziale} Teorema (Fagin)

∃SO = NP

(55)

Il Teorema di Fagin

∃Xⁿ¹. . . . ∃Xⁿ^m.F

al second’ordine esistenziale} Teorema (Fagin)

∃SO = NP

(56)

Il Teorema di Fagin

∃Xⁿ¹. . . . ∃Xⁿ^m.F

al second’ordine esistenziale}

Teorema (Fagin)

∃SO = NP

(57)

Il Teorema di Fagin

∃Xⁿ¹. . . . ∃Xⁿ^m.F

al second’ordine esistenziale}

Teorema (Fagin)

∃SO = NP

(58)

E il Tempo Polinomiale Deterministico?

I La logica predicativa è, come abbiamo visto, troppo debole per i nostri scopi.

I D’altro canto, quella al second’ordine risulta troppo potente.

I Cosa serve alla logica predicativa per catturare esattamente il tempo polinomiale deterministico?

I Consieriamo il vocabolario relativo ai grafi, ossia quello in cui l’unico simbolo relazionale E è binario e rappresenta l’adiacenza tra nodi.

I Il fatto che un nodo y sia raggiungibile in un numero non specificato di passi da x non è esprimibile in logica predicativa.

I Ci vorrebbe qualcosa come un nuovo predicato, cioè “il più piccolo” tra tutti quelli che soddisfano la seguente

“equazione”:

E^∗(x, y) ≡ x = y ∨ ∃z.(E(x, z) ∧ E^∗(z, y))

(59)

E il Tempo Polinomiale Deterministico?

“equazione”:

E^∗(x, y) ≡ x = y ∨ ∃z.(E(x, z) ∧ E^∗(z, y))

(60)

E il Tempo Polinomiale Deterministico?

“equazione”:

E^∗(x, y) ≡ x = y ∨ ∃z.(E(x, z) ∧ E^∗(z, y))

(61)

E il Tempo Polinomiale Deterministico?

“equazione”:

E^∗(x, y) ≡ x = y ∨ ∃z.(E(x, z) ∧ E^∗(z, y))

(62)

Formule Positive e Loro Minimi Punti Fissi

I Consideriamo un formula predicativa al prim’ordine F in cui le variabili libere sono:

I Una variabile al second’ordine X^m;

I m variabili al prim’ordine x1, . . . , xm.

I Tale formula predicativa si dice X^m-positiva se ogni occorrenza di X^m in F è nello scope di un numero pari di negazioni.

I Data un’interpretazione I per A_n, possiamo pensare a F come ad un funzionale F^I su P(A^m_n), ossia il seguente:

D 7−→{(a1, . . . , am) ∈ I^m | (A_n, I), ξ |= F, dove ξ(X^m) = D e ξ(xi) = ai}

Lemma

Per ogni F che sia X^m-positiva, il funzionale F^I è monotono, e ammette quindi un punto fisso µ^IX^m(x₁, . . . , x_m).F .

(63)

Formule Positive e Loro Minimi Punti Fissi

Lemma

(64)

Formule Positive e Loro Minimi Punti Fissi

Lemma

(65)

Logica Predicativa e Minimi Punti Fissi

I Le formule della logica predicativa con minimi punti fissi sono le stesse della logica predicativa al prim’ordine, ma tra i simboli predicativi ve ne sono anche nella forma

LFP (X^m, x1, . . . , xm, F ) dove F è una formula X^m-positiva.

I Alle nuove formule si può dare semantica nel modo seguente:

(A, I),ξ |= LFP (X^m, x1, . . . , xm, F )(t1, . . . , tm) sse (Jt¹K

(A,I)

ξ , . . . ,Jt^mK

(A,I)

ξ ) ∈ µ^IX^m(x1, . . . , xm).F. I A questo punto

FO (LFP ) = {struct(F ) | F è una formula

predicativa con minimi punti fissi} Teorema (Immerman, Vardi)

FO (LFP ) = P

(66)

Logica Predicativa e Minimi Punti Fissi

(A,I)

ξ , . . . ,Jt^mK

(A,I)

ξ ) ∈ µ^IX^m(x1, . . . , xm).F.

I A questo punto

predicativa con minimi punti fissi} Teorema (Immerman, Vardi)

FO (LFP ) = P

(67)

Logica Predicativa e Minimi Punti Fissi

(A,I)

ξ , . . . ,Jt^mK

(A,I)

ξ ) ∈ µ^IX^m(x1, . . . , xm).F.

I A questo punto

predicativa con minimi punti fissi}

Teorema (Immerman, Vardi) FO (LFP ) = P

(68)

Logica Predicativa e Minimi Punti Fissi

(A,I)

ξ , . . . ,Jt^mK

(A,I)

ξ ) ∈ µ^IX^m(x1, . . . , xm).F.

I A questo punto

predicativa con minimi punti fissi}

Teorema (Immerman, Vardi) FO (LFP ) = P

(69)

In Conclusione

Corollary

P = NP se e solo se FO (LFP ) = ∃SO .

I In questo modo, un problema di complessità può essere ridotto ad un problema riguardante l’espressività di due logiche.

I Se si riuscisse a dimostrare che la quantificazione

esistenziale al second’ordine non può essere espressa con i punti fissi. . .

I A tutt’oggi, non si è ancora riusciti a dimostrare alcunché, purtroppo.

(70)

In Conclusione

Corollary

(71)

In Conclusione

Corollary

(72)

In Conclusione

Corollary