Complessità in spazio Flashcards
(12 cards)
Cos’è la complessità in spazio di una Macchina di Turing (MdT)?
Sia M mdt a k nastri, in cui il nastro di input e di sola lettura
scM(n)=massimo numero di celle utilizzate (sia scritte che solo lette) da M sui nastri di lavoro dato input di lunghezza n
- def uguale per det e non det
- M può non terminare
- scM>0
Come si confronta la complessità spaziale rispetto a quella temporale?
M MdT a 2 nastri tcM(n)=f(n) => scM <= f(n)+1
Caso peggiore si ha quando in corrispondenza di ogni transizione la testina accede ad una cella di lavoro nuova
Come si confronta la complessità temporale rispetto a quella spaziale?
scM(n)=f(n) => tcM <= m(n+2)f(n)t^f(n)
Supponiamo che termini su ogni input, non può trovarsi due volte in stessa configurazione (loop)
max transizioni è maggiorato dal num.tot di configurazioni divrse che M puo assumere
m = #stati
t = |Sigma|
#stati * #posnastroinput * # #posnastrolavoro * #contenutonastro2
Cosa sono PSpace e NPSpace?
PSpace = {L linguaggio | existsM MdT det. che accetta L t.c. scM(n)=O(n^k), k>=1}
NPSpace = {L linguaggio | existsM MdT non det. che accetta L t.c. scM(n)=O(n^k), k>=1}
È vero che P ⊆ PSpace? La relazione è stretta o sono uguali?
L in P => M MdT det accetta L in tcM(n)=p(n) polinomio => scM(n) in O(p(n)) => L in PSpace
È vero che PSpace ⊆ Exp? La relazione è stretta o sono uguali?
L in PSpace => M MdT che accetta L t.c. scM(n)=p(n) => tcM(n)=O(t^f(n)) => L in Exp
È vero che NP ⊆ PSpace?
Segue dal fatto che spazio può essere riutilizzato
L NP => M MdT non det che accetta L con tcM(n)=p(n) polinomio
MdT N che accetta L a 3 nastri
codifico conputazioni O(p(n))
simulazione O(p(n))
input
scM(n)=O(p(n)) => L in PSpace
Cosa afferma il Teorema di Savitch? Qual è il suo corollario?
Sia L accettato da M MdT non det con scM(n)=f(n) allora exists N MdT det che accetta L con scM(n)=O(f(n)^2)
Usiamo M a 2 nastri
#transizioni per ogni computazione di M su stringa lunga n = O(2^{c*scM(n)})
Dato x
Cx –> C* conf. accettante unica
reachable(C, C’, j) vero quando esiste computazione che da C arriva C’ in meno di 2^j passi
C* vuol dire che reachable(Cx, C*,cscM(n)) è vero
Procedura ricorsiva per valutare reachable
j = 0 allora se C=C’ o C->C’ in 1 transizione allora vero
j != 0 C->~C->C’
forall ~C configurazione reachable(C, ~C, j-1)
reachable(~C, C’, j-1)
se entrambi veri allora vero
phi(j): spazio richiesto per eseguire algoritmo
phi(j)=f(j-1) (che riuso per entrambi i lati) + O(s(d)) = f(j-2) + 2O(s(n))=f(j-k)kO(s(n))=> jO(s(n))
j = c*s(n)) => f(j)=O(s(n)^2)
Perché si ha che PSpace = NPSpace?
Per il teorema di savitch se M MdT nn det accetta L in scM(n)=O(f(n)) allora esiste N MdT che accetta L in scM(n)=O(f^2(n)) che è sempre polinomiale
Cosa significa che un problema è PSpace-difficile o PSpace-completo?
PSpace-difficile : forall Q in PSpace esiste una riduzione polinomiale da Q a L.
Se L in PSpace-difficile e L in PSpace allora L PSpace-completo
Se L è PSpace-difficile e L ∈ P, allora P = PSpace?
Voglio mostrare che PSpace in P
L PSpace diff vuol dire per ogni Q in PSpace esiste f rid. pol da Q a L, L in P => esiste M MdT che accetta L in p(n) polinomio
Algoritmo:
- calcolo f(w) (hp1) Q -> L
- f(w) in L (hp 2)
Se L è PSpace-difficile e L ∈ NP, allora NP = PSpace?
Analogo a quello sopra (11)
