Teoria Descrittiva della Complessità

7/25/2019 Teoria Descrittiva della Complessit

1/33

Appunti di Teoria descrittiva della complessita

Alessandro Achille, Giovanni Paolini

21 dicembre 2014


2/33

2


3/33

Indice

1 Definizioni 5

1.1 Macchine di Turing deterministiche . . . . . . . . . . . . . . . . . . . . . 51.2 Macchine di Turing alternanti e non deterministiche . . . . . . . . . . . . 71.3 Codifica e decodifica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

2 Classi di complessita 11

2.1 Introduzione . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 Inclusioni tra le classi di complessita . . . . . . . . . . . . . . . . . . . . 132.3 Relazione tra ATIME e DSPACE . . . . . . . . . . . . . . . . . . . . . . 142.4 Relazione tra ASPACE e DTIME . . . . . . . . . . . . . . . . . . . . . . 152.5 Relazione tra NSPACE e ATIME . . . . . . . . . . . . . . . . . . . . . . 172.6 Alcune conseguenze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

3 Caratterizzazione di P 19

3.1 Sintassi e semantica di FO(LFP),,+ . . . . . . . . . . . . . . . . . . . . 193.2 FO(LFP),,+ equivale a P . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4 Caratterizzazione e proprieta di NP 254.1 NP equivale ad ESO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254.2 Giochi di EhrenfeuchtFrasse . . . . . . . . . . . . . . . . . . . . . . . . 254.3 ESOmon non e uguale a co-ESOmon . . . . . . . . . . . . . . . . . . . . . 274.4 NP-completezza di SAT . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

3


4/33


5/33

Capitolo 1

Definizioni

1.1 Macchine di Turing deterministiche

Una macchina di Turing deterministica, detta anche semplicemente macchina di Turing,puo essere immaginata come un dispositivo libero di muoversi su un nastro infinito sulquale in ogni istante possono essere scritti finiti simboli appartenenti ad un alfabetofinito. La macchina di Turing e dotata di uno stato, e lavora nel modo seguente.

1. Legge il simbolo scritto sul nastro nella posizione in cui si trova attualmente.

2. Controlla in una tabella finita memorizzata al suo interno cosa deve fare quandolegge quel simbolo nello stato in cui si trova.

3. Basandosi su quello che ha letto nella tabella scrive un simbolo sul nastro, si spostaa destra o a sinistra e passa in un nuovo stato.

4. Se lo stato in cui si trova ora e uno stato speciale, chiamato terminale, la macchinasi ferma. Altrimenti il processo reinizia.

Allistante zero la macchina si trova in uno stato speciale detto inizialee sul nastro puoessere gia scritta una stringa finita detta inputdella macchina. Diamo ora la definizioneformale.

Definizione 1.1.1. Si dice macchina di Turing una tupla M=Q, ,b,,q0, g dove:

1. Q e un insieme finito non vuoto di stati;

2. e un insieme finito di simboli, detto alfabeto della macchina;

3. b e un simbolo speciale, detto blank, che rappresenta una cella vuota;

4. q0 Q e lo stato iniziale;

5. g:Q {, accept, reject}indica per ogni stato se questo e non terminale, ter-minale accettanteo terminale rifiutante(luso del simbolo e per compatibilitacon la Definizione1.2.1).

5


6/33

6 Capitolo 1. Definizioni

6. : Q Q ( \ {b}) {L, R, S} e una funzione parziale detta funzione ditransizione.

Osservazione 1.1.2. Con questa definizione abbiamo scelto di non permettere alla

macchina di Turing di cancellare una cella (ovvero di scrivere il simbolo blank). Questonon modifica la potenza della macchina e permette di definire piu facilmente lo spaziousato.

Definizione 1.1.3. Data una macchina di Turing M = Q, ,b,,q0, g, chiamiamoconfigurazione della macchina una terna q,S,n dove:

1. q Q rappresenta lo stato in cui si trova attualmente la macchina;

2. S Z, con S(k) = b per tutti tranne al piu finiti k Z, rappresenta lo statoattuale del nastro;

3. n Z rappresenta la posizione attuale della macchina di Turing sul nastro.

Nel seguito useremo la seguente notazione piu compatta per descrivere la configura-zione di una macchina di Turing.

Definizione 1.1.4. Data una macchina di Turing M = Q, ,b,,q0, g, chiamiamoconfigurazione della macchina una funzione S : Z ( Q) tale che S(k) =b pertutti tranne al piu finiti k Z ed esiste unico n Z con S(n) = (, q) Q. Srappresenta lo il contenuto attuale del nastro, nla posizione della macchina di Turing e

qil suo stato nella configurazione S.

Definizione 1.1.5. Sia data una macchina di Turing M = Q, ,b,,q0, g e due sueconfigurazioni S e S. Siano n Z, , q Q gli unici tali che S(n) = (, q) esupponiamo (, q) = (q, , R). Diciamo cheM puo fare la transizione da S a S, e loindichiamo con SMS, se

1. S(n) =;

2. S(n+ 1) = (, q) per un qualche ;

3. S(k) =S

(k) per ogni kZ

diverso da ne n + 1.

La definizione si adatta facilmente ai casi in cui (, q) = (q, , L/S).

Osservazione 1.1.6. Per ogni configurazione Sdella macchina di Turing M, esiste alpiu una S tale che SMS, da cui laggettivo deterministica.

Definizione 1.1.7. Una configurazione si dice accettante se lo stato corrispondente eaccettante, oppure se puo fare una transizione in una configurazione accettante. Vice-versa diciamo che e rifiutante se lo stato corrispondente e rifiutante, oppure se puo fareuna transizione in una configurazione rifiutante.


7/33

Capitolo 1. Definizioni 7

Definizione 1.1.8. Data una macchina di Turing M=Q, , b , , q 0, g, una sua confi-gurazione Ssi dice iniziale seS(0) = (, q0) per un qualche in . In tal caso, il conte-nuto del nastro si dice inputdella macchina di Turing e questo determina totalmente laconfigurazione iniziale.

Definizione 1.1.9. SiaSw la configurazione iniziale con inputw in . Diciamo che una

macchina di TuringMaccetta linputw, e lo indichiamo conM(w) Yse la configurazioneSw e accettante. Viceversa diciamo cheMrifiuta linputw, e lo indichiamo conM(w) N,se la configurazione Sw e rifiutante.

Definizione 1.1.10. Dato un alfabeto , chiamiamo problema decisionale un insiemedi stringhe finite A . Diciamo che il problema A e calcolabile dalla macchina diTuringMse, per ogni w in ,M accettaw se e solo se w e inA e M rifiutaw se e solow non e in A. Diciamo che il problema A e calcolabile se e calcolabile da una macchinadi Turing.

Esistono varianti della definizione di macchina di Turing che, pur non cambiandolinsieme dei problemi calcolabili, sono piu semplici da adoperare in alcuni casi. Unavariante utile sono le macchine di Turing a k nastri. Queste funzionano esattamentecome le macchine di Turing standard ma ad ogni passaggio leggono e scrivono contem-poraneamente su tutti e k i nastri. La funzione di transizione sara dunque del tipo : Q k Q ((\ {b}) {L, R, S})k. Una macchina di Turing a k nastri puochiaramente simulare una macchina di Turing a un solo nastro. Vale anche il viceversa,come descritto dal seguente risultato.

Fatto 1.1.11. Una macchina di Turing a un solo nastro puo simulare una macchina di

Turing a k nastri. In particolare tutti i problemi calcolabili da una macchina di Turinga k nastri sono calcolabili anche da una macchina di Turing a un solo nastro.

Il modello di macchina di Turing che useremo piu spesso e quello di una macchinadi Turing con un nastro di input e un nastro di lavoro. Questa segue le stesse regoledi una macchina di Turing a due nastri, fatta eccezione del fatto che non puo scriveresul nastro di input, ma solo leggere, e che in una sua configurazione iniziale il nastrodi lavoro e sempre vuoto. Se una macchina di Turing di questo tipo termina con inputw, definiamo lo spazio di lavoro usato su input w come il numero di celle del nastro dilavoro non vuote nella configurazione terminale.

1.2 Macchine di Turing alternanti e non determini-

stiche

Una macchina di Turing alternate puo essere pensata come una normale macchina di Tu-ring che ad ogni transizione puo sdoppiarsi e provare piu strade contemporaneamenteper risolvere il problema.

Definizione 1.2.1. Una macchina di Turing alternante e una tupla M=Q, ,b,,q0, gdove:


8/33


Q e un insieme finito non vuoto di stati;

e un insieme finito di simboli, detto alfabeto della macchina;

b e un simbolo speciale, detto blank, che rappresenta una cella vuota;

: Q P(Q {L, R, S});

q0 Q e lo stato iniziale;

g : Q {, , accept, reject} indica per ogni stato se questo e esistenziale,universale, accettanteo rifiutante.

Per una macchina di Turing alternante valgono le stesse definizioni che abbiamo datoper le macchine di Turing deterministiche, fatta eccezione per la definizione di transizionee di configurazione accettante, che modifichiamo come segue.

Definizione 1.2.2. Sia data una macchina di Turing alternante M=Q, ,b,,q0, gedue sue configurazioni S e S. Siano n Z, , q Q gli unici tali che S(n) = (, q)e supponiamo (q, , R) (, q). Diciamo che M puo fare la transizione da Sa S, e loindichiamo con SMS

, se

1. S(n) =;

2. S(n+ 1) = (, q) per un qualche ;

3. S(k) =S(k) per ogni k Z diverso da ne n + 1.

La definizione si adatta facilmente al caso (q, , L/S)(, q).

Osservazione 1.2.3. Per una generica macchina di Turing alternante non e piu veroche per ogni configurazione Sesiste al piu una configurazione S tale che SMS.

Definizione 1.2.4. Una configurazione di una macchina di Turing alternante si diceaccettante se vale una delle seguenti:

il suo stato e accettante;

il suo stato e esistenziale e la configurazione puo fare una transizione in unaconfigurazione accettante;

il suo stato e universale, la configurazione puo fare almeno una transizione e ognitransizione che la configurazione puo fare finisce in una configurazione accettante.

Viceversa si dice rifiutante se vale una delle seguenti:

il suo stato e rifiutante;

il suo stato e esistenziale, la configurazione puo fare almeno una transizione e ognitransizione che la configurazione puo fare finisce in una configurazione rifiutante;


9/33

Capitolo 1. Definizioni 9

il suo stato e universale e la configurazione puo fare una transizione in una confi-gurazione rifiutante.

Possiamo infine definire cosa significa che una macchina di Turing alternante Maccetti un input w allo stesso modo della Definizione1.1.9.

Definizione 1.2.5. Chiamiamo macchina di Turing non deterministicauna macchinadi Turing alternante in cui tutti gli stati sono esistenziali, accettanti o rifiutanti.

Osservazione 1.2.6. Una macchina di Turing deterministica puo essere vista come uncaso particolare di una macchina di Turing non deterministica dove ogni stato pu o fareuna transizione in al piu unaltro stato.

Uno strumento molto utile nello studio delle macchine di Turing alternati e il grafodelle configurazioniGM:

Definizione 1.2.7. Data una macchina di Turing alternante M con un unico statoaccettante, il grafo delle configurazioni GM e la struttura sul linguaggio L= E, G, G, tdefinita da:

linsieme Vdei vertici del grafo coincide con linsieme di tutte le possibili configu-razioni di M;

gli archi del grafoErappresentano le possibili transizioni, ovvero valeE(S, S) SMS

;

G V e unetichetta dei nodi che indica le configurazioni con stato esistenziale;

G V e unetichetta dei nodi che indica le configurazioni con stato universale;

t V e una costante che indica lunica configurazione avente nastro vuoto e statoaccettante.

Questo grafo descrive completamente tutte le possibili computazioni di Mcon inputqualsiasi. Spesso siamo interessati a una particolare computazione con input w fissato,per cui diamo anche la seguente definizione.

Definizione 1.2.8. Il grafo GM,w della computazione di M con input w e dato dallastruttura (V , E , G, G, s , t) ottenuta estendendo GM con una costante s, che denota la

configurazione iniziale con input w. Se non ce ambiguita al posto di GM,w scriveremosemplicementeGw.

Dato GM,w , e interessante trovare un modo per capire se una configurazione e accet-tante, in particolare se lo e la configurazione iniziale s, guardando solo il grafo.

Definizione 1.2.9. Data un grafo alternante G, ovvero una struttura nel linguaggioL = {E, G, G, s , t}, definiamo Ealt(x, y) essere la piu piccola (rispetto allinclusione)relazione binaria su G tale che

Ealt(x, y)(x= y) z

E(x, z) Ealt(z, y)

G(x) z(E(x, z) Ealt(z, y))


10/33


Che esista una minima tale relazione puo essere verificato facilmente a mano, o lo sipuo dedurre dal piu generale Corollario3.1.4.

Osservazione 1.2.10. Data una macchina di Turing alternante Me un input w, si ha

cheMaccetta linput w se e solo se GM,w |= Ealt(s, t).

Definizione 1.2.11. Indichiamo con Reachalt linsieme dei grafi alternanti finiti G talicheG|= Ealt(s, t).

1.3 Codifica e decodifica

Sia L = {Ra11 , . . . , Rass , c1, . . . , cl}un linguaggio. Vogliamo fornire un modo standard di

codificare una L-struttura finita A come stringa binaria, che denoteremo bin(A). Nelseguito supporremo sempre, senza perdita di generalita, che il dominio di unaL-struttura

finita sia un insieme del tipo{1, . . . , n} N

.Definizione 1.3.1. Sia A una L-struttura, con |A| = n < +. Se R Ak e unarelazione, definiamo bin(R) :|A|k {0, 1}come:

bin(R)(a1+a2 n+. . .+ak nk1) :=

1 se R(a1, . . . , ak)

0 altrimenti

Se a e un elemento di A = {1, . . . , n}, definiamo bin(a) come la scrittura binaria delnumero a, con eventualmente aggiunti degli zeri a sinistra affinche abbia lunghezzaesattamentelog2(n). Definiamo infine

bin(A) := bin(R1) . . . bin(Rs)bin(c1) . . . bin(cl).

Osservazione 1.3.2. Detta nla cardinalita di A, la lunghezza della codifica e

| bin(A)|= na1 +. . .+nas +l log2(n),

e in particolare e polinomiale inn. Inoltre, dato che il membro di destra e strettamentecrescente in n, conoscendo solamente il linguaggio L e la codifica bin(A) possiamo ricavaren e piu in generale possiamo ricostruire tutta la struttura A. Infatti avremo che valeRAi (x1, . . . , xai) se e solo se bin(A)(n

a1 + . . . + nai1 + x1+ x2 n + . . . + xai nai1) = 1.

Useremo questa procedura principalmente per descrivere modelli allinterno di mac-

chine di Turing. Infatti, come notato nellOsservazione1.3.2,una macchina di Turing puoricostruire il valore della relazioneRAi (x1, . . . , xai) calcolando il valore di n, spostando latestina e leggendo il valore nella posizionena1 +. . .+nai1 +x1 +x2 n+ . . .+xai n

ai1 delblocco di memoria corrispondente alla codifica. Nello pseudo-codice indicheremo questaprocedura con decodeRi(bin(A), x1, . . . , xai). La corrispondente procedura per leggere ilvalore di una costante sara indicata con decodeci(bin(A)).

Definizione 1.3.3. Fissato un linguaggio L ci riferiremo a un insieme A diL-strutturefinite come a un problema decisionale, intendendo con questo che consideriamo il corri-spondente problema bin(A) ={bin(A)| A A}nel senso della Definizione1.1.10.


11/33

Capitolo 2

Classi di complessita

2.1 Introduzione

Definizione 2.1.1. Sia t : N N una funzione. Diciamo che una macchina di Turingalternante M lavora in tempo t(n) se per ogni input w la macchina Maccetta o rifiutaw e basta esaminare solo le configurazioni fino al tempo t(|w|) per decidere se linputverra accettato o rifiutato.

Definizione 2.1.2. Sia s: N N una funzione. Diciamo che una macchina di Turingalternante Mlavora in spazio s(n) se per ogni input w la macchina Maccetta o rifiutaw e basta esaminare le configurazioni in cui la testina ha distanza minore di s(|w|)dallorigine per decidere se linput verra accettato o rifiutato.

Definizione 2.1.3. Siat : N Nuna funzione. Un problema decisionale A appartienead ATIME(t(n)) se esistono una macchina di Turing alternanteMe una costante >0tale che M lavora in tempo t(n) e Mcalcola il problema A. Similmente diremo cheil problema e in NTIME(t(n)) se la macchina M puo essere presa non deterministica ein DTIME(t(n)) se puo essere presa deterministica.

Definizione 2.1.4. Sias : N Nuna funzione. Un problema decisionaleA appartienead ASPACE(s(n)) se eiste una macchina di Turing alternante M e una costante >0tale che Mlavora in spazio s(n) e Mcalcola il problema A. Similmente diremo cheil problema e in NSPACE(s(n)) se la macchinaM puo essere presa non deterministica ein DSPACE(s(n)) se puo essere presa deterministica.

Risulta molto interessante il concetto di computabilita in tempo o spazio polinomiale.Per questo definiamo le classi di complessita DPTIME e DPSPACE nel seguente modo:

DPTIME =kN

DTIME(nk), DPSPACE =kN

DSPACE(nk).

Analogamente si definiscono le classi NPTIME, APTIME, NPSPACE ed APSPACE.Particolarmente studiate sono le classi DPTIME e NPTIME, le quali vengono piu comu-nemente denominate P ed NP, rispettivamente. Non e noto se P sia incluso strettamentein NP o se valga luguaglianza.

11


12/33

12 Capitolo 2. Classi di complessita

La classe NP ha una caratterizzazione equivalente: un problema decisionale A ap-partiene ad NP se e solo se esistono dei certificati che consentono di verificare in tempopolinomiale che una struttura A appartenga ad A. Piu formalmente, vale la seguenteproposizione.

Proposizione 2.1.5. Sia A un problema decisionale su un linguaggio L. Si ha cheA NP se e solo se esistono una macchina di Turing deterministica M e un polinomiop(n) tali che:

per ogni stringa binaria c di lunghezza p(| bin(A)|) (detta certificato), lamacchinaMsu input bin(A)c termina in tempo p(| bin(A)|);

per ogni L-struttura A, si ha che A Ase e solo se esiste una stringa binaria c dilunghezza p(| bin(A)|) tale che M(bin(A)c) Y.

Dimostrazione. Supponiamo che A appartenga ad NP. Allora esiste una macchina diTuring non deterministica N che determina in tempo polinomiale se una struttura Aappartiene a S. Possiamo supporre senza perdita di generalita che tutte le scelte nondeterministiche di N siano binarie. Definiamo una macchina deterministicaM che, suinput bin(A)c, simula lesecuzione di N su input bin(A) sostituendo (per ogni i) lai-esima scelta non deterministica con la scelta deterministica descritta dalli-esimo bitdella stringac. Nel caso in cui la stringac non sia sufficientemente lunga, Mtermina inuno stato rifiutante. Notiamo che Aappartiene a Sse e solo seN(bin(A)) Y, ovvero see solo se esiste una sequenza di scelte (che possiamo codificare con la stringa binaria c)che portano in una configurazione finale accettante diN. In altre parole,A appartiene a

Sse e solo se M(bin(A)c) Y. Il tempo di calcolo di M e polinomiale in bin(A), perchelo e quello di N. Definiamo allora p(n) come un qualsiasi polinomio tale che M terminiin tempo p(| bin(A)|).

Supponiamo ora che esista una macchina di Turing determinista Mcon le caratteri-stiche enunciate. SiaNuna macchina non deterministica che, su input bin(A), simulaM scegliendo non deterministicamente i simboli di c man mano che M li utilizza. Se-gue dalle definizioni che N(bin(A)) Y se e solo se esiste una stringa binaria c tale cheM(bin(A)c) Y. Il tempo di calcolo di N e polinomiale in bin(A), perche lo e quello diM(indipendentemente dalla lunghezza di c).

Il seguente corollario e una semplice riscrittura della proposizione e ci sara utile inseguito.

Corollario 2.1.6. Sia A NP un problema decisionale su un linguaggioL. Allora esisteunk N e una macchina di Turing deterministicaMtale che, per ogniL-struttura finitaA, si ha che A appartiene ad A se e solo se esiste una relazione k-aria R Ak per cuiM(bin(A) bin(R)) Y.

Dimostrazione. Basta notare che, data una struttura |A|, ogni stringa binaria di lun-ghezza minore di |A|k puo essere ottenuta come bin(R), con R una relazione k-aria suA. Si conclude utilizzando la proposizione precedente.


13/33

Capitolo 2. Classi di complessita 13

Per ogni classe di complessita Csi puo introdurre la classe dei problemi complemen-tari, costituita per lappunto dagli elementiAc al variare diA C. Solitamente una taleclasse viene indicata aggiungendo il prefisso co alla denominazione della classe C. Peresempio, co-NP e la classe dei problemi decisionali i cui complementari appartengono aNP. Si puo dare la seguente caratterizzazione di co-NP, analoga a quella che abbiamoappena dato di NP.

Proposizione 2.1.7. Sia A un problema decisionale su un linguaggio L. Si ha cheA co-NP se e solo se esiste una macchina di Turing deterministica Mtale che:

la macchinaMsu input bin(A)ctermina in tempo polinomiale rispetto a | bin(A)|,per ogni stringa binaria c;

per ogni L-struttura A, si ha che A A se e solo se esiste una stringa binaria ctale che M(bin(A)c) Y.

Dimostrazione. Segue immediatamente applicando la Proposizione2.1.5ad Ac.

Osservazione 2.1.8. P = co-P. Di conseguenza, se fosse vero che P = NP, allora NPsarebbe anche uguale a co-NP. In altre parole, NP = co-NP implica P= NP.

2.2 Inclusioni tra le classi di complessita

Nel resto del capitolo dimostreremo diverse inclusioni interessanti tra le varie classi dicomplessita. Tali inclusioni possono essere riassunte nel seguente schema:

DTIME(t(n)) NTIME(t(n)) ATIME(t(n))

DSPACE(t(n)) NSPACE(t(n)) ASPACE(t(n)) =

= DTIME(O(1)t(n)) . . .

dove con la notazione DTIME(O(1)t(n)) indichiamo la classe

c> 0

DTIME(ct(n)).

Oltre a quelle precedentemente rappresentate, vale anche linclusione NSPACE(t(n)) ATIME(t(n)2).

Le inclusioni presenti sulle righe dello schema precedente sono tutte ovvie: ci o che puoessere fatto con una macchina deterministica puo essere fatto anche con una macchinanon deterministica, e cio che puo essere fatto con una macchina non deterministica puo es-sere fatto anche con una macchina alternante. Nel resto di questo capitolo dimostreremole inclusioni e le uguaglianze rimanenti, e ne trarremo poi alcune conseguenze.


14/33


2.3 Relazione tra ATIME e DSPACE

Teorema 2.3.1. ATIME(t(n))DSPACE(t(n)).

Dimostrazione. Data una macchina di Turing alternanteMche lavora in ATIME(t(n)),vogliamo trovare una macchina di Turing deterministica che lavori in DSPACE(t(n)) eaccetti gli stessi input w di M. Supponiamo per semplicita di notazione che ogni statonon deterministico di Mpossa fare una transizione in al piu due stati. Sia Gw il grafodella computazione della macchinaMsu input w. Esibiamo una macchina di Turing Nche lavora in DSPACE(t(n)) la quale, preso in input un nodo del grafo, decide se quelnodo e accettante o meno. Cio consente di concludere, poiche la macchina M accettalinput w se e solo se il nodo iniziale di Gw e accettante.

La macchinaNdeve verificare se il nodo iniziale diGw sia accettante o meno. Lideaper fare questo e di visitare ricorsivamente il grafo, il quale risulta tuttavia troppo grande

per essere salvato interamente in memoria. La soluzione che adottiamo e di memorizzaresolo il nodo iniziale c0, il nodo c che stiamo attualmente visitando e il percorso cheabbiamo fatto per raggiungerlo a partire dal nodo iniziale, ovvero una stringa binariaP = b1, b2, . . . , bn che ci dica per ogni nodo alternante che abbiamo incontrato se cisi e spostati sul primo o sul secondo figlio. Teniamo inoltre in memoria un simboloD {S, N, ?} che ci dice se abbiamo gi a verificato che quel nodo e accettante, nonaccettante oppure se ancora non lo sappiamo.

Si noti che, in particolare, non vengono tenute in memoria tutte le configurazionilungo il percorso da c0 a c. Di conseguenza, ogniqualvolta si debba passare da un nodoc al suo padre, risulta necessario percorrere nuovamente il cammino da c0 a c (che puoessere ricostruito grazie alla stringa binaria P).

Vediamo ora i dettagli dellalgoritmo di visita ricorsiva del grafo.

SeD e uguale a?, non abbiamo ancora stabilito se il nodo c sia o meno accettante.Pertanto, se c ha dei figli modifichiamo lo stato nel modo seguente:

P :=b1, b2, . . . , bn, 0, D:= ?, c:= figlio sinistro di c.

In caso contrario, c e una foglia. Di conseguenza corrisponde a uno stato in cui lamacchina Mha terminato la computazione, per cui e possibile determinare se sitratti di un nodo accettante o non accettante. Modifichiamo allora lo stato in

P :=b1, b2, . . . , bn, D:= S/N, c:= c,

dove D assume il valore S se lo stato c e accettante, mentre assume il valore N selo stato c e non accettante.

SeD e in{S, N}e P =, ci troviamo nel nodo iniziale c0 e sappiamo se tale nodoe accettante. Quindi la computazione di N puo terminare, restituendo D comerisultato.

Se D e in {S, N} e P =b1, b2, . . . , bn con n 1, abbiamo determinato se il nodocorrentece accettante e dobbiamo continuare la visita dellalbero di computazione.


15/33


1. Se il padre di c corrisponde ad uno stato esistenziale e D = S, allora il padredi c non puo che essere accettante, per cui passiamo nello stato

P :=b1, b2, . . . , bn1, D:= S, c:= padre di c.

2. Analogamente se il padre dic corrisponde ad uno stato universale e D = N, ilpadre di c e sicuramente non accettante, dunque passiamo nello stato

P :=b1, b2, . . . , bn1, D:= N, c:= padre di c.

3. Sebn = 0 (ovveroc e un figlio sinistro) e non ci troviamo in nessuno dei primidue casi, il padre di c e accettante se e solo se il figlio destro del padre di c eaccettante. Passiamo pertanto nello stato

P :=b1, b2, . . . , bn1, 1, D:= ?, c:= figlio destro del padre di c.

4. Se bn= 1 (ovvero c e un figlio destro) il padre di c e accettante se e solo se ce accettante. Di conseguenza passiamo nello stato

P :=b1, b2, . . . , bn1, D:= D, c:= padre di c.

Esaminiamo infine la memoria utilizzata dalla macchina di Turing N. La macchinaM lavora in tempo O(t(n)), per cui la codifica di un singolo nodo di Gw occupa spazioO(t(n)). La lunghezza della stringa binaria P e data al massimo dalla profondita delgrafo Gw, che e sempre O(t(n)). Infine, memorizzare D richiede spazio O(1). Possiamoquindi concludere che la macchina Nlavora effettivamente in DSPACE(t(n)).

2.4 Relazione tra ASPACE e DTIME

Teorema 2.4.1. ASPACE(t(n)) = DTIME(O(1)t(n)).

Dimostrazione. Linclusione ASPACE(t(n)) DTIME(O(1)t(n)) puo essere dimostratain modo analogo al Teorema 2.3.1. Piu nel dettaglio, data una macchina di Turing Mche lavora in ASPACE(t(n)), si costruisce una macchina di Turing Nche visita il grafoGw della computazione diMsu inputw e determina se w sia o meno accettante per M.

La dimensione del grafo Gw e O(1)t(n), perche il numero di configurazioni accessibili dauna singola configurazione e limitato da una costante che dipende solo da M, e non daw. Effettuiamo la visita del grafo in modo simile a quanto descritto nella dimostrazionedel Teorema2.3.1,salvando in un nastro i nodi incontrati nel percorso dalla radice finoal nodo corrente, e in un altro nastro la lista di tutti i nodi gia visitati. Per ciascunnodo gia visitato c salviamo anche unetichetta Dc, appartenente allinsieme {S, N, ?},che indica se la corrispondente configurazione e accettante, rifiutante oppure non ancoradeterminata (questultima possibilita accade se la visita ricorsiva dei figli non si e ancoraconclusa). Quando inizia la visita di un nuovo nodo c, la macchina Nesegue le seguentioperazioni.


16/33


Controlla se c e gia stato visitato, scandendo lintera lista dei nodi visitati.

Se c e gia stato visitato e ha etichetta Dc = S oppure Dc = N, si ritorna al padredi c e si continua la visita.

Se c e gia stato visitato e ha etichetta Dc = ?, cio significa che c era gia statoincontrato nel percorso dalla radice ac. Osserviamo che tale eventualita puo effet-tivamente accadere anche seMtermina su inputw: infatti, affinche una macchinaalternante termini, non e necessario che tutti i rami della computazione terminino(cfr. Definizione1.2.4). Sicuramente pero, ai fini del determinare se la configura-zione c e accettante, percorrere un ciclo nel grafo Gw e inutile. Di conseguenza, seci si trova in questo caso, si ritorna al padre diccome secfosse rifiutante (ma senzamodificare letichetta Dc = ?, perche nel seguito della computazione si potrebbescoprire che in realta c e accettante).

Sec non e stato ancora visitato, lo aggiungiamo alla lista dei nodi visitati ponendoDc=?, e visitiamo ricorsivamente i figli di c.

Il numero di visite ai nodi del grafo e dellordine del numero di archi, il quale eproporzionale al numero di nodi (perche il grado di ogni nodo e O(1)). Osserviamo chenella visita di ciascun nodo loperazione piu costosa e data dalla scansione della lista deinodi visitati, la quale ha lunghezza

O(1)t(n) O(t(n)) =O(1)t(n)+O(log t(n)) =O(1)t(n).

In conclusione, il tempo impiegato dalla macchina N e

O(1)t(n) O(1)t(n) =O(1)t(n).

Dimostriamo ora linclusione DTIME(O(1)t(n)) ASPACE(t(n)). Sia M una mac-china di Turing che lavora in DTIME(ct(n)) per qualche c > 0; vogliamo definire unamacchina di Turing N che lavori in ASPACE(t(n)), accettando gli stessi input che ac-cettaM. Possiamo assumere senza perdita di generalita che Mabbia un unico nastro.Lidea e di definire una subroutine ricorsiva di N, che chiamiamo C(t,p,a), al terminedella quale N accetta se (nellesecuzione di M su input w) al tempo t in posizione pvi e il simbolo a, altrimenti rifiuta. Seguiamo la convenzione chea possa appartenerea (nel caso in cui non vi sia la testina) oppure a Q (se vi e la testina, nel qual

caso lelemento di Q indica lo stato attuale della macchina). Vediamo ora i dettaglisullimplementazione di questa subroutine.

Losservazione principale e che lesito della chiamata a C(t,p,a) e univocamente de-terminato dallesito delle chiamate a C(t 1, p, a) al variare di p {p 1, p, p+ 1}ed a Q. Introduciamo uno stato qC in cui la macchina Ndeve iniziare adeseguire la subroutine C. Supponiamo cheNsia nello stato qC, e che abbia in memoria(su un apposito nastro di lavoro dedicato allinizializzazione della subroutineC) la terna(t,p,a). Se t = 0, Naccetta se e solo se nella posizione p dellinput w (tenendo contodelleventuale presenza della testina) vi e il simbolo a. Se invece t > 0, N esegue leseguenti operazioni.


17/33


Sceglie (non deterministicamente) tre elementi a1, a0, a1 in Q.

Verifica se la macchina M con i simboli a1, a0, a1 in posizioni p 1, p, p + 1(rispettivamente) avrebbe al passo successivo il simbolo a in posizione p. In caso

affermativo continua, altrimenti rifiuta.

Si porta in uno stato universale e sceglie (non deterministicamente) i {1, 0, 1}.

Scrive sul nastro dedicato allinizializzazione di C la terna (t 1, p+ i, ai) e siriporta nello stato qC, in modo da chiamare ricorsivamente la subroutine C.

Limplementazione della subroutine C e sufficiente per determinare se un qualsiasiinputwvenga accettato daM: basta controllare che al tempoct(n) la macchinaMsi trovinello stato accettante. Osserviamo infine che la macchinaNche abbiamo definito lavora

effettivamente in ASPACE(t(n)), poiche oltre allinputw deve memorizzare solamente leseguenti variabili: un intero t (compreso tra 0 ect(n), che quindi occupaO(t(n)) bit), uninterop(di modulo ct(n)), dei simboli a, a1, a0, a1 (che occupano O(1) bit), un interoi compreso tra 1 e 1 (che occupa 2 bit).

2.5 Relazione tra NSPACE e ATIME

Teorema 2.5.1. NSPACE(t(n)) ATIME(t(n)2).

Dimostrazione. Sia Muna macchina di Turing che lavora in NSPACE(t(n)). Vogliamo

definire una macchina N che lavori in ATIME(t(n)2) e che accetti gli stessi input cheaccetta M. Sia w un input, e sia Gw il grafo della computazione di M su input w.Lidea e di fare in modo cheNimplementi una subroutine ricorsivaP(d,x,y), al terminedella quale Naccetta se in Gw esiste un cammino lungo al piu 2

d dal nodoxal nodoy,altrimenti rifiuta.

Entriamo ora maggiormente nei dettagli. Introduciamo uno stato esistenziale qP, incui N inizia lesecuzione della subroutine P leggendo le variabili d,x,y da un appositonastro. Sed = 0, la macchinaNaccetta nel caso in cui x = y oppurex My, altrimentirifiuta. Se invece d >0, Nesegue le seguenti operazioni.

Si porta in uno stato esistenziale e sceglie (non deterministicamente) un nodo zdiGw. Tale zrappresenta un possibile nodo intermedio in un eventuale percorso daxa y.

Si porta in uno stato universale e sceglie (non deterministicamente) un bit b. Talebit determina se verificare lesistenza di un percorso da x a zoppure se verificarelesistenza di un percorso da za y.

Seb = 0, si porta nello stato qP inizializzandoPcon le variabili (d,x,z). Se inveceb= 1, si porta nel medesimo stato ma inizializzando Pcon le variabili (d,z,y). Daquesto momento in avanti, lesecuzione continua ricorsivamente.


18/33


La procedura descritta ha leffetto desiderato, perche lesistenza di un percorso da x a yin 2d passi e equivalente allesistenza di un nodo intermediozper cui si possa andareda xa z in 2d1 passi e da za y in2d1 passi.

La subroutineP e sufficiente per decidere se un inputw venga accettato daM, poichebasta che N chiami Pcon i seguenti parametri:

x= configurazione iniziale di Msu input w;

y= configurazione finale accettante di M;

d= logaritmo della profondita del grafo Gw.

Si noti che la profondita del grafo Gw e al massimo ct(n) per qualche costante c >0 (che

dipende da Mma non da w), quindi d= O(t(n)).Verifichiamo infine cheNlavori effettivamante in ATIME(t(n)2). Per quanto appena

osservato, il numero di chiamate alla subroutine P e O(t(n)). Ciascuna delle chiamate(compresa quella finale con d = 0) impiega tempo O(t(n)), perche la lunghezza dellacodifica di un qualsiasi nodo di Gw e O(t(n)). Quindi il tempo totale di esecuzione eeffettivamenteO(t(n)2).

2.6 Alcune conseguenze

Esaminiamo infine alcuni risultati che si dimostrano a partire dalle inclusioni descrittenelle sezioni precedenti.

Corollario 2.6.1. NPSPACE APTIME.

Dimostrazione. E sufficiente applicare il Teorema2.5.1,osservando che il quadrato di unpolinomio e ancora un polinomio.

Corollario 2.6.2. NPSPACE = DPSPACE.

Dimostrazione. Abbiamo che NSPACE(t(n)) ATIME(t(n)2) DSPACE(t(n)2). Dalmomento che il quadrato di un polinomio e ancora un polinomio, ne deduciamo cheNPSPACE = DPSPACE.

Quindi il problema P vs NP e molto piu semplice da risolvere rimpiazzando il tempo

con lo spazio.


19/33

Capitolo 3

Caratterizzazione di P

3.1 Sintassi e semantica di FO(LFP),,+

Definizione 3.1.1. Sia (S2, x , y) una formula. Diremo che S compare in posizionepositiva in se tutte le volte in cui compare e preceduta da un numero pari di negazioni.Piu precisamente, per induzione sulla complessita della formula:

S e in posizione positiva in tutte le formule atomiche (che la contengano o no);

seScompare in posizione positiva in e , allora compare in posizione positiva in , ,x(x), x(x);

seScompare in posizione positiva in allora compare in posizione negativa in,

e in ;

seScompare in posizione positiva in allora compare in posizione negativa in e viceversa se S compare in posizione negativa in allora compare in posizionepositiva in .

Definizione 3.1.2. Estendiamo la sintassi di FO introducendo un nuovo quantificatore,che indichiamo con LFP. Data una formula del primo ordine(S2, x , y) in cuiScomparein posizione positiva, lespressione LFPS,x,y(S

2, x , y) avra il tipo di una relazione binariacon variabili libere FV()\{S,x,y}. Chiameremo la sintassi cos ottenuta FO(LFP),,+.

Semanticamente vogliamo interpretare LFPS,x,y(S,x,y) come la piu piccola (rispet-to allinclusione) relazione binaria R tale che R(x, y) (R,x,y), ma dobbiamo primaverificare che una tale relazione esista.

Teorema 3.1.3 (Tarski-Knaster). SiaA un insieme finito e sia f :P(Ak) P(Ak) unafunzione monotona rispetto allinclusione (i.e. se SS allora f S f S). Allora esisteun minimo punto fisso dif, che indicheremo con LFP f, e per la precisione questo e datoda f|A|

k

().

Dimostrazione. Dato che f e monotona e A e finito, deve esistere un n N tale chefn() = fn+1(), e inoltre tale n puo essere preso minore di |A|k. Indichiamofn()

19


20/33

20 Capitolo 3. Caratterizzazione di P

con S. Per definizione S e un punto fisso di f. Se S e un altro punto fisso di f, datoche S e che f e monotona, avremo S = fk() fk(S) = S. Quindi S e il piupiccolo punto fisso.

Corollario 3.1.4. Sia (S,x,y) una L-formula del primo ordine in cui Scompare inposizione positiva, e sia Auna L-struttura. Indichiamo con f : P(A A) P(A A)la funzione

f,A(R) :={(a, b)A A| (S,x,y)A,R,a,b}.

Questa funzione e monotona sulle relazione ordinate per inclusione. Il suo piu pic-colo punto fisso LFP f,A e la piu piccola relazione R A A tale che R(a, b)

(S,x,y)A,R,a,b.

Definizione 3.1.5. Usando le notazioni del Corollario 3.1.4, estendiamo la funzione

semantica di FO ad FO(LFP),,+ ponendo

LFPS,x,y(S,x,y)M = LFP f,M.

3.2 FO(LFP),,+ equivale a P

Lemma 3.2.1. FO P. In altre parole, per ogni L-formula chiusa in FO esiste unamacchina di Turing T in P tale che, data una L-struttura A, si ha A |= se e solose T(bin(A)) Y. Inoltre leT possono essere costruite in modo che siano logaritmichenello spazio.

Dimostrazione. Procediamo per induzione strutturale sulla complessita della formula .

Sia atomica nel linguaggio L = {Ra1 , . . . , Rak , c1, . . . , cl}; allora deve essere nellaforma c1 = c2 oppure nella forma Rs(c1, . . . , ck), dove i ci sono simboli di costante.La macchina di Turing T come prima cosa leggera dal nastro di input i valori micorrispondenti alle costanti ci. Se era nella forma c1 = c2 allora basta controllareluguaglianza di m1 ed m2. Se invece era nella forma Rs(c1, . . . , ck), leggiamo il bit inposizione m1+ m2 n + . . . + mk n

k1 del blocco relativo alla relazione Rk e accettiamonel caso abbia valore 1.

Se e combinazione booleana di formule i, la macchina di Turing corrispondente si

ottiene facilmente mettendo insieme le macchine di Turing delle singole i.Sia infine nella forma x(x). Detto L il linguaggio ottenuto aggiungendo a L

un simbolo di costante c, la L-formula (c) ha complessita minore di quella di edunque, per ipotesi induttiva, esiste una macchina di Turing T(c) che gli corrisponde.Notiamo che, dato x {0, . . . , n 1}, possiamo trasformare A in una L struttura(A, x) interpretando la costante c con x. Costruiamo allora la macchina di Turing Tin modo che T(bin(A)) accetti se e solo se T(c)(bin(A)bin(x)) accetta per qualchex. Piu concretamente, per ogni x {0, . . . , n 1} scriviamo su un nastro a partebin(A) bin(x) e lanciamo la macchina T(c) usando questo come nastro di input. SeT(c) accetta, fermiamo la computazione e accettiamo.


21/33

Capitolo 3. Caratterizzazione di P 21

Proposizione 3.2.2. FO(LFP),,+ P. In altre parole, per ogni L-formula chiusa in FO(LFP),,+ esiste una macchina di Turing T in P tale che, data una L-strutturaA, si ha A|= se e solo se T(bin(A)) Y.

Dimostrazione. Rispetto al lemma precedente dobbiamo solo considerare in piu il caso : LFPS,x,y(S,x,y)(a, b), con a, b costanti. Notiamo che possiamo vedere(S,x,y)come una formula chiusa nel linguaggio L =L {S2, x , y}, dunque, sfruttando lipotesiinduttiva, ha senso considerare la macchina di Turing T(S,x,y) ad essa corrispondente.Inoltre, usando le notazioni del Corollario3.1.4,si haT(S,x,y)(bin(A,R,a,b)) Y se e solose (a, b) f,A(R). Questa osservazione, insieme alla dimostrazione del Teorema3.1.3,suggeriscono il seguente algoritmo per T e ne dimostrano la correttezza.

functionT(bin)R 0fori < max2 do

forh, k= 0..maxdoif T(S,x,y)(bin(A)bin(h)bin(k)) Y then

R[a max+b] 1end if

end for

end for

adecodea(bin)b decodeb(bin)returnR[a max+b]

end function

Dimostriamo ora linclusione inversa, ovvero P FO(LFP),,+. La dimostrazione sibasa sui seguenti claim.

Claim 1 P = ASPACE(log(n)).

Claim 2 Reachalt FO(LFP),,+.

Claim 3 SeA e un problema in ASPACE(log(n)), allora A FOReachalt.

Dimostrati questi tre claim, per concludere, basta notare che un problema che si riduceFO a un problema in FO(LFP),,+ e a sua volta in FO(LFP),,+. Il Claim 1 segue dalTeorema2.4.1prendendo t(n) = log(n). Dimostriamo dunque gli altri due.

Proposizione 3.2.3. Reachalt FO(LFP),,+;

Dimostrazione. La relazione Ealt(x, y) e piu piccolo punto fisso della formula

(S,x,y) :(x= y) z

E(x, z) S(z, y)

G(x) z(E(x, z) S(z, y))

(cfr. Definizione 1.2.9). Dato che S compare in posizione positiva, possiamo scrivereEalt(a, b) : (LFPS,x,y(S,x,y))(a, b). In particolare Ealt e definibile in FO(LFP),,+,da cui segue facilmente la tesi.


22/33


Proposizione 3.2.4. Se A e un problema in ASPACE(log(n)), allora A FOReachalt.In particolare, Reachalt e un problema P-completo.

Dimostrazione. Sia = {Ra11 , . . . , Rarr , c1, . . . , cs} un linguaggio eMuna macchina di Tu-

ring in ASPACE(c log(n)) che accetta come input la codifica binaria di una -struttura.Dobbiamo mostrare che esiste un modo per associare ad ogni-strutturaAdi cardinalitan un grafo alternante I(A) = (VA, GA , G

a, E

a, sA, tA), definibile al primo ordine in A,tale che:

M(bin(A)) I(A) Reachalt .

Lidea e di associare alla struttura A il sottografo del grafo della computazione di Msu input bin(A) dato dalle configurazioni di Min cui la testina del nastro di lavoro hadistanza dallorigine minore di c log(n); in questo modo la nostra richiesta sara automa-ticamente soddisfatta (cfr. Definizione2.1.2). A tal fine identifichiamo il dominio di A

con linsieme{1, 2, . . . , n}e scegliamo come insieme di vertici V

A

linsiemeA

4+a+c

, cona= max(a1, . . . , ar). In questo modo un vertice iddel grafo puo essere identificato conuna tupla di numeri naturali minori di n:

id= p1, . . . , p4, r1, . . . , ra, w1, . . . , wc

Ciascuna di queste tuple rappresentera una possibile configurazione della macchina M.Per la precesione:

p1 {1, . . . , r}rappresenta la relazione che la macchina sta leggendo sul nastro diinput;

p2 QMrappresenta lo stato in cui si trova la macchina di Turing;

p3 {0, . . . , c log(n)}rappresenta la posizione della testina sul nastro di lavoro;

p4 {, }indica se lo stato attuale e esistenziale o universale;

w1, . . . , wc nc = 2c log(n) rappresenta una possibile configurazione del nastro di

lavoro (stiamo usando il fatto che M e in ASPACE(c log(n));

r1, . . . , rc nc = r1 +r2n+ . . .+ ran

a1 < na rappresenta la posizione della

testina sul nastro di input.

Ora che abbiamo definito il dominio VA del grafo dobbiamo definire le relazioni EA,GA , G

A , s e t. Di queste, G e G sono immediate (basta guardare il valore di p4), per

quanto riguardas, puo essere definita come

s(id) :(p1 = 1 p2=q0 p3 = 0 r= 0 w= 0),

e anche t puo essere definita in maniera simile. Concentriamoci dunque su EA: dob-biamo trovare una relazione E(x, y) tale che valga E(id, id) se e solo se nel grafo dellecomputazioni diMcon input bin(A) ce un arco tra la configurazione corrisponente a id


23/33

Capitolo 3. Caratterizzazione di P 23

quella corrispondente a id. Come prima cosa sia R una regola della macchina di TuringMnella forma

q, w, i q, o, w, i,

dove q e lo stato attuale, w il simbolo letto sul nastro di lavoro, i il simbolo letto sulnastro di input, q lo stato in cui si fa la transizione, o il simbolo scritto sul nastro di la-voro,w {1, 0, 1}lo spostamento sul nastro di lavoro ei {1, 0, 1}lo spostamentosul nastro di input. Associamo a Rla relazione

CR(id, id) :

1ir

p1 = i p2=q p4=g(q) BIT( w, p3)

w Ri(r1, . . . , rai)i

p2 = q p4 = g(q

) p3 = p3+w BIT( w, p3)

o

p=p3(BIT( w, p) BIT( w, p))

(spostamento testina di input)dove BIT( w, p) e vera se e solo se ilp-esimo bit del numerow1 +w2 max+ . . .+wc max

c1

e 1 (BIT e definibile in FO,,+, si veda ad esempio [2, 1.17]). La parte della formulaindicata con spostamento della testina descrive in che modo sono rapportate r,r, p1,p1 e i. Sebbene sia concettualmente simile alla parte gia scritta, e molto piu laboriosa, eabbiamo preferito tralasciarla. Notiamo che valeCR(id, id

) se e solo se la configurazionecorrispondente a id puo passare alla configurazione corrispondente a id mediante laregola R. Per concludere definiamo allora

E(id, id) : R CR(id, id).E facile convincersi della correttezza di questa definizione.

Osservazione 3.2.5. Nella dimostrazione precedente avremmo potuto memorizzare tut-te le possibili configurazioni del nastro di lavoro allinterno del grafo grazie allipotesiM ASPACE(c log(n)), ma non possiamo fare lo stesso per il nastro di input che halunghezza polinomiale in n (e quindi il numero di possibili configurazioni e esponenzialeinn). Tuttavia, come visto, possiamo limitarci a memorizzare soltanto la posizione dellatestina sul nastro di input.

Corollario 3.2.6. P FO(LFP),,+. In altre parole, per ogni macchina di Turing Mche accetta o rifiuta una -struttura A in tempo polinomiale, esiste una -formulainFO(LFP),,+ tale che A|= se e solo se M(bin(A)) Y


24/33



25/33

Capitolo 4

Caratterizzazione e proprieta di NP

4.1 NP

equivale adESO

La dimostrazione seguente fa uso della caratterizzazione di NP data nel Corollario 2.1.6e della caratterizzazione di P ottenuta nel capitolo precedente, nonche del fatto seguente.Per la dimostrazione svolta a lezione si veda invece [2, 7.2].

Fatto 4.1.1 ([1]). In strutture finite, ESO(LFP) senza punti fissi annidati equivale adESO.

Teorema 4.1.2 (Fagin). NP = ESO.

Dimostrazione. SiaA un problema in NP. Per il Corollario 2.1.6esistono una macchinadi Turing Mche lavora in tempo polinomiale e un k N tali che A A se e solo seM(bin(A) bin(R)) Y per una qualche relazione R di arieta k su A. Per il Corollario3.2.6, esiste una formula in FO(LFP),,+ tale che M(bin(A)bin(R)) Y se e solo seA, R |= . Dunque vale A A se e solo se A |= R(k). Concludiamo applicando ilFatto4.1.1alla formula R(k).

Viceversa, data una formula in ESO, mostriamo che esiste una macchina di Tu-ring non deterministica Nche lavora in tempo polinomiale e tale che A |= se e solo

se N(bin(A)) Y. Sia R , con in FO. Per la Proposizione 3.2.2 esiste una

macchina di Turing Mche lavora in tempo polinomiale tale che A,R |= se e solo se

M(bin(A) bin( R)) Y. Notiamo che bin(A)bin( R) ha lunghezza polinomiale rispetto a

|A|, dunque M con input bin(A) bin( R) termina ancora in tempo polinomiale rispettoa |A|. Costruiamo la macchina Nin modo che scelga in modo non deterministico le re-

lazioni R(equivalentemente i bit della stringa bin( R), che e polinomiale in|A|) e quindi

simuli Mcon input bin(A)bin( R).

4.2 Giochi di EhrenfeuchtFrasse

Definizione 4.2.1. Siano A, B due L-strutture. Descriviamo il gioco di Ehrenfeu-chtFrasseGk(A, B) di duratak N. Vi sono due giocatori indicati con i simboli e

25


26/33

26 Capitolo 4. Caratterizzazione e proprieta di NP

. A ogni turno il giocatore sceglie un elemento daA o daB . Il giocatore cerca diimitarlo scegliendo un elemento corrispondente nellaltra struttura. Dopo k turni sonostati scelti degli elementi a1, . . . , ak A e b1, . . . , bkB . Il giocatore vince il gioco se

A, a1, . . . , ak QF B, b1, . . . , bk,

ovvero se, per ogni formula (x1, . . . , xk) senza quantificatori, vale A|=(a1, . . . , ak) see solo se B|=(b1, . . . , bk).

Definizione 4.2.2. Date due L-strutture A e B, diciamo che A EFk B se e solo se ilgiocatore ha una strategia vincente per il gioco di EF Gk(A, B).

Definizione 4.2.3. Date due L-strutture A e B, diciamo che Ak B se e solo se perogni formula con rango di quantificazione RQ() k vale A|= se e solo se B|=.

Osservazione 4.2.4. Date due L-strutture A eB, valeA0B se e solo se A QF B evale A B se e solo se per ogni k N vale Ak B.

Lemma 4.2.5. Ci sono solo un numero finito di classi di k-EF-equivalenza din-uple; inparticolare, seC(n, k) e linsieme di tali classi, si ha che |C(n, k +1)| s|C(n+1,k)|. Inoltreper ogni classe H = [A, a1, . . . , an] C(n, k) esiste una formula H con RQ(H) ktale che:

1. A|=H(a1, . . . , an);

2. Se B|=H(b1, . . . , bn), allora (A, a1, . . . , an)EFk (B, b1, . . . , bk).

Dimostrazione. Per induzione su k. Supponiamo k = 0. Allora A, a1, . . . , an EF0

B, b1, . . . , bn se e solo se A,a verifica le stesse atomiche di B,b. Ma, dato che il lin-guaggio e finito e non ci sono simboli di funzione, ci sono solo finite formule atomicheR1(x), . . . , Rr(x). Quindi H e caratterizzata dalla formula

H(x1, . . . , xn) :

i:A|=Ri(a)

Ri(x)

j:A|=Rj(a)

Rj(x)

Svolgiamo ora il passo induttivo. Per ipotesi induttiva sappiamo che una qualsiasi H

C(n+ 1, k) e caratterizzata da una formula (x1, . . . , xn+1). Ad ogni C(n+ 1, k)associamo la formula

(x1, . . . , xn) :H

xn+1H(x1, . . . , xn+1) H

xn+1H(x1, . . . , xn+1)

Osserviamo che RQ() k + 1 poiche, per ipotesi induttiva, RQ(H) k. Linsie-me di tutte le coerenti (cioe aventi un modello) caratterizza le classi in C(n, k+ 1).Infatti, sia data una struttura A e una n-upla a1, . . . , an. Definiamo C(n+ 1, k)come linsieme delle H C(n+ 1, k) tali che A |= yH(a1, . . . , an, y). Per costruzio-ne A, a1, . . . , an |= (x1, . . . , xn). Mostriamo ora che se B, b1, . . . , bn |= (x1, . . . , xn)


27/33

Capitolo 4. Caratterizzazione e proprieta di NP 27

allora B, b1, . . . , bn EFk+1 A, a1, . . . , an. A tal fine supponiamo, senza perdita di gene-

ralita, che il giocatore scelga al primo turno un elemento a in A. La classe H =[A, a1, . . . , an, a] e in C(n+ 1, k) e, dato che B, b1, . . . , bk |=(x1, . . . , xk), ne segue cheB |= yH(b1, . . . , bk, y). Sia allorab tale che B |= H(b1, . . . , bk, b). Per ipotesi indut-tiva B, b1, . . . , bk, b

EFk A, a1, . . . , ak, ae quindi il giocatore ha una strategia vincente

scegliendo b.

Teorema 4.2.6. Date due L-strutture A e B, se A EFk B alloraA k B. Supponendoin piu che L sia un linguaggio finito senza simboli di funzioni, vale anche il viceversa,ovvero Ak B implica A

EFk B.

Dimostrazione. Supponiamo che valga AEFk B. Per dimostrare che A k B procedia-mo per induzione su k. Il passo base k = 0 segue dallosservazione precedente e dalledefinizioni. Supponendo il risultato vero per k, dimostriamolo per k+ 1. Sia la piu

piccola formula di rango di quantificazionek + 1 su cui i due modelli sono in disaccordo.Possiamo suppore senza perdita di generalita che y(y) e che esista aA tale cheA |= (a). Per la definizione di gioco di EF di durata k+ 1, esiste un b B tale cheA, a EFk B, b. Per ipotesi induttiva questo implica cheA, a k B, b, e in particolare,essendo RQ((y)) =k, che B|=(b), da cui B|=y(y).

Viceversa, supponiamoA, a1, . . . , ank B, b1, . . . , bn, siaH= [A, a1, . . . , an] e siaHcome nel Lemma4.2.5. Dato che RQ(H) k, vale B|=H(b1, . . . , bn) e dunque per illemma si ha A, a1, . . . , an

EFk B, b1, . . . , bn.

4.3 ESOmon

non e uguale a co-ESOmon

Sebbene non si sappia se NP = co-NP, si puo dimostrare un risultato simile: ESOmon =co-ESOmon. Per fare questo utilizzeremo i giochi di EF, introdotti nella Sezione 4.2.

Definizione 4.3.1. Sia A una L-struttura. Il grafo di Gaifman di A e il grafo nonorientato GA= (|A|, E

A) dove GA|=E(a, b) se e solo se ae bsono distinti e sono partedi una tupla (c1, . . . , cr) di elementi di A tali che A |= R(c1, . . . , cr) per una qualcherelazione r-aria R L.

Osservazione 4.3.2. Se L = {E} e il linguaggio dei grafi (con ununica relazione E

binaria) e A e un grafo non orientato, allora GA=A.

Definizione 4.3.3. Data una L-struttura A, ln-intornoSA(n, a) di un elemento a Ae la sottostruttura di A definita nel seguente modo:

SA(n, a) ={b A | dGA(a, b) n}.

Sia inoltre

SA(n, a1, . . . , ak) =k

i=1

SA(n, ai).


28/33


Definizione 4.3.4. Siano (A, a) e (B, b) due L-strutture puntate. Diciamo che essesono n-equivalenti secondo Gaifman se esiste un isomorfismo di strutture tra SA(n, a)ed SB(n, b) che manda a in b. La notazione che useremo per indicare la n-equivalenzasecondo Gaifman e la seguente: (A, a)G

n

(B, b).

Definizione 4.3.5. Chiamiamon-tipo diainAla classe di equivalenza di (A, a) rispettoalla relazioneGn .

Definizione 4.3.6. Date dueL-strutture A e B , diciamo cheA Gn B se per ognin-tipo, A e B hanno lo stesso numero di elementi di n-tipo.

Osservazione 4.3.7. Se AGn B, allora AGk B per ogni k < n.

Teorema 4.3.8. AG3n B implica AEFn B.

Dimostrazione. Mostriamo una strategia vincente per il giocatore nel gioco di Ehren-feuchtFrasseGn(A, B). Dimostriamo per induzione sul numero k di mosse giocate (con0 k n) che il giocatore e in grado di preservare il seguente invariante:

SA(3nk, a1, . . . , ak), a1, . . . , ak

=

SB(3nk, b1, . . . , bk), b1, . . . , bk

,

dove lisomorfismo e diL-strutture. Chiamiamok un tale isomorfismo (la cui esistenzaverra dimostrata induttivamente).

Passo base (k= 0). E banalmente vero poiche entrambe le strutture sono vuote.

Passo induttivo (kimplicak+1). Supponiamo senza perdita di generalita che il gio-catore scelga, come (k + 1)-esima mossa, lelementoa = ak+1 A. Distinguiamodue casi.

Primo caso: aSA(2 3nk1, ai) per qualche i {1, . . . , k}. Allora lintornoSA(3

nk1, a) e completamente contenuto in SA(3nk, ai). Di conseguenza e

sufficiente che il giocatore giochi lelemento b = k(a): lisomorfismok+1si ottiene semplicemente restringendo k a SA(3

nk, a1, . . . , ak).

Secondo caso: aSA(2 3nk1, a1, . . . , ak). Sia il 3nk1-tipo dia in A. Peripotesi induttiva, gli insiemiSA(23nk1, a1, . . . , ak) e SB(23

nk1, b1, . . . , bk)

contengono lo stesso numero di elementi di tipo. Per differenza (usando lipo-tesiAG3n B), anche i complementari di questi due insiemi contengono lo stes-so numero di elementi di tipo , quindi esistebSB(23

nk1, b1, . . . , bk) con lostesso 3nk1 tipo dia. Osserviamo cheSA(3

nk1, a) eSA(3nk1, a1, . . . , ak)

sono disgiunti, e similmente ancheSB(3nk1, b) e SB(3

nk1, b1, . . . , bk) sonodisgiunti. Di conseguenza lisomorfismok, ristretto a SA(3

nk1, a1, . . . , ak),puo essere esteso ad un isomorfismo

k+1 : SA(3nk1, a1, . . . , ak, a) SB(3

nk1, b1, . . . , bk, b)

che manda ainb.


29/33


Per k = n si ha in particolare che A, a1, . . . , an QF B, b1, . . . , bn. Pertanto quella cheabbiamo mostrato e effettivamente una strategia vincente per il giocatore .

Corollario 4.3.9. AG3n B implica An B .

Dimostrazione. Segue dai Teoremi4.3.8e4.2.6.

Nel resto di questa sezione utilizzeremo il linguaggioL = {E} dei grafi orientati, doveE e una relazione binaria. Introduciamo il problema decisionale Connected, al qualeappartengono tutti e soli i grafi connessi. Dimostreremo che tale problema appartiene aco-ESOmon ma non ad ESOmon.

Lemma 4.3.10. Connectedco-ESOmon.

Dimostrazione. Dobbiamo esprimere la proprieta di essere sconnesso con una formula inESOmon. Una condizione equivalente ad essere sconnesso e che linsieme dei vertici possa

essere partizionato in due sottoinsiemi non vuoti per cui non esistono archi dal primoverso il secondo. Questa condizione puo essere espressa mediante la seguente formulaESOmon:

U(1), W(1)

xU(x) xW(x) x

U(x)W(x)

x, y

U(x) W(y) E(x, y)

.

Quindi Connected co-ESOmon.

Lemma 4.3.11. ConnectedESOmon.

Dimostrazione. Supponiamo per assurdo che esista una L-formulaP(1)1 , . . . , P (1)r , con

FO, tale che per ogni grafo orientato G = (VG, EG) si abbia

G|= ( P) G connesso.

Sia m = RQ(), e sia = {E, P1, . . . , P r} un nuovo linguaggio che estende L in cuile Pi sono relazioni unarie. Osserviamo che una -struttura puo essere consideratacome un grafo colorato con 2r colori, dove il colore del vertice x e codificato dai bitP1(x), . . . , P r(x).

Sia un numero naturale sufficientemente grande rispetto a m ed r (sara chiaro inseguito cosa si intende con sufficientemente grande). SiaG = (VG, EG) un grafo ciclicosu vertici, con gli archi orientati tutti nello stesso verso. Essendo G connesso, soddisfa

la formula ( P). In altre parole esiste una -struttura A= (|A|, EA, PA1 , . . . , P Ar ), con|A|= VG ed EA =EG, tale che A|=. Rappresentiamo A come un grafo colorato con2r colori (vedi Figura4.1).

Avendo preso sufficientemente grande, esistono sicuramente due vertici a, b |A|dello stesso 3m-tipo e con SA(3

m, a) SB(3m, b) = . Siano a e b i vertici del grafo

che vengono immediatamente prima di a e b, come nella Figura4.1. SiaB la-strutturaottenuta da A mantenendo le stesse relazioni unarie (cioe ponendo PBi = P

Ai per ogni

i= 1, . . . , r) ma cambiando alcuni archi: rimuoviamo gli archi daa ada e dab ab, edaggiungiamo gli archi da a ab e dab ada. ComeL-struttura, B e un grafo costituitoda due cicli disgiunti.


30/33


Lidea di questa costruzione e che, localmente, i grafi colorati A e Bsono indistinguibi-li fino a distanza 3m; piu formalmente, si ha cheA G3m B. Allora, per il Corollario4.3.9,possiamo dedurre che A m B. Dato che A |= e che RQ() = m, si ha anche che

B |= . Conseguentemente il grafoH = (|B|, EB) soddisfa la formula ( P), dunquedeve essere connesso. Ma questa e una contraddizione, percheH e costituito da due ciclidisginti.

a a

bb

a a

bb

Figura 4.1: Esempio delle strutture A(sulla sinistra) e B (sulla destra), per = 8.

Teorema 4.3.12. ESOmon = co-ESOmon.

Dimostrazione. Segue immediatamente dai Lemmi4.3.10e4.3.11.

4.4 NP-completezza di SAT

Il Teorema4.1.2consente di dimostrare in modo particolarmente semplice lNP-comple-tezza del problema di soddisfacibilita booleana di formule proposizionali, denominatocomunemente SAT.

Teorema 4.4.1. SAT e NP-completo.

Dimostrazione. SAT appartiene a NP, perche un certificato di soddisfacibilita di una

formula e dato dal valore da assegnare alle variabili per fare in modo che la formularisulti vera.Dobbiamo dimostrare che un qualsiasi problema A NP si riduce polinomialmente

a SAT. Supponiamo che A sia un insieme di strutture nel linguaggio L= {R1, . . . , Rt},dove R1, . . . , Rt sono relazioni di arieta b1, . . . , bt, rispettivamente. Per il Teorema4.1.2esiste una formula della forma

: S1, . . . , S r x1, . . . , xn primordine

(x1, . . . , xk) senza quantificatori

tale cheA sia dato dai modelli di .


31/33


Sia A una L-struttura, e sia n = |A|. Abbiamo cheA appartiene a A se e solo sesoddisfa la formula , ovvero se e solo se esistono delle relazioni SA1 n

a1 , . . . , S Ar nar tali che sia soddisfatta x1, . . . , xn (x1, . . . , xk). Questo e equivalente a trovareunassegnazione che renda vera la formula proposizionale

:

0c1,...,ck


32/33



33/33

Bibliografia

[1] Jan Van den Bussche, Introduction to finite model theory, http://dtai.cs.kuleuven.be/krr/files/seminars/IntroToFMT-janvdbussche.pdf, consultato il18 dicembre 2014.

[2] N. Immerman, Descriptive complexity, Graduate texts in computer science, Springer

New York, 1999.

33
http://dtai.cs.kuleuven.be/krr/files/seminars/IntroToFMT-janvdbussche.pdfhttp://dtai.cs.kuleuven.be/krr/files/seminars/IntroToFMT-janvdbussche.pdfhttp://dtai.cs.kuleuven.be/krr/files/seminars/IntroToFMT-janvdbussche.pdfhttp://dtai.cs.kuleuven.be/krr/files/seminars/IntroToFMT-janvdbussche.pdf

Teoria Descrittiva della Complessità

Documents

Transcript of Teoria Descrittiva della Complessità