Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Aniello Murano » 20.PSPACE completezza


Definizione di Pspace Completezza

Definizione: Un linguaggio B è PSPACE-completo se soddisfa le seguenti due condizioni:

1. B è in PSPACE, e
2. Ogni A in PSPACE è riducibile in tempo polinomiale a B.

Se B soddisfa solo la condizione 2, diremo che è PSPACE-hard.

E’ importante notare che utilizziamo ancora la riduzione in tempo piuttosto che quella in spazio

Non usiamo quella di spazio perchè non vogliamo che la complessità del problema sia assorbita nella trasformazione.

Problema TQBF


PSPACE-completezza di TQBF

Teorema: TQBF è PSPACE-completo

Per mostrare che TQBF∈PSPACE, usiamo un algoritmo in spazio polinomiale che assegna valori di verità alle variabili e ricorsivamente valuta la formula.

Per l’hardness, procediamo in maniera similare a quanto fatto per NP.

  • Mostriamo che A≤pTQBF per ogni APSPACE, iniziando con una macchina M che lavora in spazio polinomiale per A.
  • Dunque, usiamo una riduzione in tempo polinomiale che mappa una stringa w ad una formula φ che codifica una simulazione di M su input w.
  • φè vera se e solo se M accetta w.

Algoritmo in spazio polinomiale per TQBF

Il seguente algoritmo decide TQBF: T = “Con input <φ>, una fully quantified Boolean formula:
1. Se φ non contiene quantificatori, allora è un espressione con solo costanti così valutiamo φ e accept se è true, altrimenti, reject.
2. Se φ è ∃xψ, ricorsivamente chiamiamo T su ψ, prima con 0 sostituito a x e poi con 1 sostituito a x. Se il loro risultato è accept, Allora accept;
altrimenti, reject.
3. Se φ è ∀xψ, ricorsivamente chiamiamo T su ψ, prima con 0 sostituito a x e poi con 1 sostituito a x. Se entrambi risultano accept, allora accept;
altrimenti, reject.”
In pratica, valutiamo la formula con una procedura val nel modo seguente:

  • val(VERO)=vero e val(FALSO)=falso
  • val(¬Φ)=¬val(Φ), val(Φ1\/Φ2)=val(Φ1)\/val(Φ2) e val(Φ1/\Φ2)=val(Φ1)/\val(Φ2)
  • val( xΦ)=val(Φ | x=VERO) \/ val(Φ | x=FALSO)
  • val( xΦ)=val(Φ | x=VERO) /\ val(Φ | x=FALSO)

Ad ogni chiamata ricorsiva abbiamo una formula ridotta dove alcune variabili vengono instanziate. Tutta la ricorsione richiede dunque memoria vari a |Φ|. La profondità massima della ricorsione è pari al più alla lunghezza della formula. Dunque, una quantità di memoria totale (|Φ|)2 è sufficiente.

PSPACE-Hardness per TQBF

Dimostriamo ora che il problema è completo. Dato un linguaggio L ∈ PSPACE, consideriamo la MT M che accetta L in spazio polinomiale.
Sia x una parola di L. Costruiamo una formula Φ di TQBF tale che Φ è vera se e solo se M accetta x in spazio nk.
Usiamo una tecnica simile a quella utilizzate nel teorema di Cook-Levin. In particolare, assumiamo che:

  • la macchina usa nastro semi-infinito;
  • ogni configurazione usa spazio nk;
  • la macchina cicla nella configurazione finale.

Si noti che in questo caso la tabella da considerare ha nk colonne e 2nk righe; quindi è di taglia esponenziale. Si veda la figura a lato.
Si ricordi che nel caso di SAT, il tableau rappresentava un ramo della computazione ed era di nk righe (e colonne)
La formula che definiremo usa una variabile per ogni cella. Per semplicità nella formula ci riferiamo alle configurazioni come entità atomica.


PSPACE-Hardness per TQBF(segue)

Sia m=nk. La formula quantificata che costruiremo è la seguente

Φ(x) = X1 X2M(X1)^φM(X2) ^ φI(X1,x) ^ φA(X2) ^ φT(X1,X2,2m))

Φ(x) può essere interpretata nel seguente modo.
X1 ed X2 sono due configurazioni (soddisfano il predicato φM).
X1 è una configurazione iniziale, contenente l’input x (soddisfa il predicato φI).
X2 è una configurazione finale (soddisfa il predicato φA).
Esiste una computazione legale della macchina M che porta da X1 a X2 in 2m passi (soddisfano il predicato φT(X1, X2,2m)).

Osservazioni alla formula

Ogni variabili Xi corrisponde ad una riga della tabella e quindi corrisponde ad m variabili del tipo ci,j.
La formula φM impone che vengano soddisfatte le proprietà di una configurazione relativa alla macchina M (espresse con le variabili ci,j),
la formula φI impone che sia soddisfatta la struttura della configurazione iniziale della macchina M con input x,
la formula φA impone che sia soddisfatta la proprietà di una configurazione finale,
la formula φT impone che siano soddisfatte le proprietà di una computazione eseguita dalla macchina M.

Ultimi passi per PSPACE-Hardness di TQBF

Il problema principale è come definire la formula _T. Infatti se la definiamo come nel teorema di Savitch abbiamo:

φT(X1,X2,p) = X3M(X3)^φT(X1,X3,t/2) ^ φT(X3,X2,t/2)

ma questo comporta una formula di lunghezza esponenziale.
Usiamo invece la definizione seguente:

φT(X1,X2,t) = X Y X3(φM(X3)^[((X=X1^Y=X3)v(X=X3^Y=X2))→φT(X,Y,t/2)])

la cui lunghezza è O(m log 2m).

Pertanto la formula φ(x) è anch’essa di lunghezza complessiva O(m2).

Formule come giochi

Ciascuna formula TQBF (in forma prenessa) φ può essere vista come un gioco tra due giocatori A ed E.
A ed E muovono a turno instanziando le variabili, secondo le seguenti regole:
Se φ =xψ(x), E muove instanziando x=0 oppure x=1.
Se φ =xψ(x), A muove instanziando x=0 o x=1.
In entrambi i casi, il gioco continua con ψ(0) o ψ(1), secondo della scelta fatta
Il gioco continua finché non sono eliminati tutti i quantificatori.
Quando non ci sono più quantificatori, diremo che il giocatore E è il vincitore se la rimanente formula è valutata true. Altrimenti vince il giocatore A.
Si consideri il seguente esempio. Chi vince?

xyz[(xvy ∧(yvz)∧(yvz)] E moves, selects x=1

yz[(1vy)∧(yvz)∧(yvz)] A moves, selects y=0

z[(1v0)∧(0vz)∧(0vz)] E moves, selects z=1

(1v0)∧(0v1)∧(0v1) A wins

Il problema formula-game

Quando E ha un modo per assegnare dei valori alle variabili tali che per ogni scelta di A la formula risulta true, allora si dice che E ha una strategia vincente.
Lo stesso dicasi per A su E se la formula risulta falsa.
Chi ha una strategia vincente in xyz[(xvy)∧(yvz)∧(yvz)] ?
E: Seleziona x=1, e seleziona z come la negazione di quello che sceglie A per y.
Chi ha una strategia vincente in xyz[(xvy)∧(yvz)∧(yvz)] ?
Questa volta A ha una strategia vincente, infatti basta scegliere y=0.

Si consideri adesso il seguente insieme.
FORMULA-GAME = {<φ> | Il giocatore E ha una strategia vincente in φ}
Teorema FORMULA-GAME è PSPACE-completo.
Dimostrazione: Questa segue dalla semplice osservazione che

FORMULA-GAME = TQBF.

  • Di fatti, φ è true se e solo se il giocatore E ha una strategia vincente nel gioco corrispondente.
    Una dimostrazione più formale di questo teorema passa attraverso il numero dei quantificatore prefisso di φ

Nelle prossime diapositive utilizzeremo FORMULA-GAME per provare la PSPACE-hardness di alcuni problemi.

Il gioco Geografy dei bambini

I giocatori, chiamati I e II, alterneranno i nomi delle città di ogni parte del mondo (inizia il giocatore I). Ogni città scelta deve iniziare con la stessa lettera che ha concluso la città precedente. Le ripetizioni non sono consentite. Il giocatore che non è in grado di continuare perde.
Siamo in grado di modellare questo gioco con un grafo orientato i cui nodi sono le città del mondo. C’è arco da una città ad un altra se la prima può portare alla seconda utilizzando le regole del gioco.
Un nodo è designato come il nodo di start. La condizione che le città non possono essere ripetute, significa che il percorso non deve ammettere cicli.


Geography generalized

In Generalized Geography, prendiamo un arbitrario grafo diretto con un nodo assegnato a start (invece del grafo associato con le attuali città). Chi ha la strategia vincente?


Geography generalized

In Generalized Geography, prendiamo un arbitrario grafo diretto con un nodo assegnato a start (invece del grafo associato con le attuali città). Chi ha la strategia vincente?


Geography generalized

In Generalized Geography, prendiamo un arbitrario grafo diretto con un nodo assegnato a start (invece del grafo associato con le attuali città). Chi ha la strategia vincente?


Geography generalized

In Generalized Geography, prendiamo un arbitrario grafo diretto con un nodo assegnato a start.


Geography generalized

In Generalized Geography, prendiamo un arbitrario grafo diretto con un nodo assegnato a start.


Geography generalized

In Generalized Geography, prendiamo un arbitrario grafo diretto con un nodo assegnato a start.


GG e Pspace-completezza

GG = {<G,b> | il giocatore 1 ha una strategia vincente per il gioco di Generalized Geography giocato sul grafo G partendo dal nodo b }

Appartenenza a PSPACE. Un algoritmo ricorsivo simile a quello usato per TQBF determina quale giocatore ha la strategia vincente. Questo algoritmo lavora in spazio polinomiale per cui GG ∈ PSPACE.

Per provare la PSPACE-hardeness, usiamo una riduzione in tempo polinomiale da FORMULA-GAME a GG.

  • Questa riduzione converte una formula game φ in un grafo generalized geography G in modo che giocare su G imita il giocare su φ.
  • In effeti i giocatori nel gioco generalized geography giocano una codifica del formula game.

Perchè GGPSPACE

Il seguente algoritmo decide GG:
M = “su input <G,b>, dove G è un grafo e b è un nodo di G:

  1. Se b ha grado uscente 0, reject, perchè il giocatore 1 perde immediatamente.
  2. Rimuovi il nodo b è tutti gli archi che sono connessi è crea un nuovo grafo H.
  3. Per ogni nodo b1,…,bk a cui b puntava originariamente, ricorsivamente chiama M su <H,bi>.
  4. Se tutte le chiamate su <H,bi> accettano, il giocatore 2 ha una strategia vincente nel gioco originale e quindi reject. Altrimenti, il giocatore 2 non ha una strategia vincente e quindi il giocatore 1 deve averne una, quindi accetta.

Perché GG è Nspace-hard

Consideriamo una formula-game φ.
Possiamo assumere che sia il primo che l’ultimo quantificatore è esistenziale () e che il quantificatore e strettamente alternato. Se non è così, facilmente portare φ a questa forma aggiungendo variabili e quantificatori inutili.
Inoltre, possiamo assumere che la parte quantifier-free di φ è una formula 3CNF, altrimenti può essere convertita in 3CNF.
Si noti che le conversioni eventualmente richieste solra producono una formula equivalente e prendono un tempo polinomiale.
Si consideri dunque la formula

φ = x1x2x3x4xk[c1c2...cm],

dove ciascun ci è una disgiunzione di tre letterali sulle variabili xi.
Descriviamo adesso un modo per convertire (in tempo polinomiale) φ in <G,b> tale che φFORMULA-GAME se e solo se <G,b>GG, cioè, E ha una strategia vincente in φ se e solo se Player I ha una strategia vincente in<G,b> .

Perché GG è Nspace-hard

La parte sinistra di G sarà rappresentata nel seguente modo:

  • Per ogni variabile creiamo un diamante.
  • Le frecce blu indicano le scelte del Giocatore I (i turni)
  • Le frecce rosse indicano le scelte del Giocatore II.
  • Le scelte che si trovano nella parte sinistra corrisponderanno alla scelta 1 nella formula di gioco, e le scelte che si trovano nella parte destra corrispon-deranno alla scelta 0.
  • Il grafo in figura è parziale e necessita di una estensione che mostriamo nella prossima diapositiva per un particolare esempio di φ .

Perchè GG è PSPACE-hard


  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion