Altre classi di complessità Flashcards
(19 cards)
Quali sono le proprietà della classe co-P?
La classe complementare a P.
Es. SAT -> not SAT=dato un pol.bool. determinare se non esiste alcun assegnamento che lo soddisfa
Cosa vuol dire co-NP?
L linguaggio t.c. neg L in NP
L NP-completo, L co-NP => NP = co-NP
L in NPC
negL in NP
⊇) Sia Q co-NP, negQ NP
L NPC esiste f rid.pol. da negQ a L
w in negQ <=> f(w) in L cioè
w notin negQ <=> f(w) not in L cioè
w in Q <=> f(w) in negL
quindi f rid. pol da Q a negL
dato w
1. calcolo f(w)
2. f(w) in negL?
Q in NP
⊆) Q in NP => negQ in co-NP (per ipotesi precedente
negQ in NP => Q in co-NP
Qual è la definizione della classe EXP?
{L linguaggio|esiste MdT che accetta L t.c. tcM(n)=O(2^n^k) esponenziale}
Perché NP ⊆ EXP? (Dimostrazione)
L in NP => esiste MdT non det che accetta L t.c. tcm(n)=O(n^k)
Def. N MdT det. che accetta L
1. eseguo tutte le computazioni di M
sia generica computazione M(m1, m2, …, m_{n^k} su input lungo n
2. #computazioni O(delta^n^k)
ciascuna richiede O(n^k)
O(delta^n^k * n^k) = O(delta^n^k) cioè L NP
Perché P ⊂ EXP? (Dimostrazione)
Vogliamo far vedere che exists L in Exp, L notin P
sia L ={(R(M),x)| se M su x termina in uno stato finale, allora ciò deve avvenire entro 2^2|x| passi}
- L in Exp. Def. N su input (R(M),x) come segue
- Eseguo M su x. se termina entro 2^2|x| accetto, altrimenti rifiuto
- Se n=|R(M),x| e se eseguo massimo 2^2|x| passi e |x|<= n supponendo che la lunghezza di R(M) sia trascurabile rispetto alla lunghezza di x (ovvero fisso R(M) e faccio crescere |x| allora
complessità in tempo di N è tcN(n)=O(2^2n)=O(4^n) esponenziale ovvero L in Exp - L not in P, faccio vedere che per ogni N MdT che accetta L tcN(n) != O(2^n)
per assurdo supponiamo N MdT che accetta L t.c. tcN(n)=2^n.
Costruiamo D MdT definita su R(M) come segue
- esegue N su (R(M), R(M))
- se N termina in stato finale, D termina in stato non finale
- se N termina in stato non finale, D termina in stato finale
D termina all’opposto
Complessità di D, n=|R(M)| è tcD(n)=tcN(2n)=2^2n
Eseguo D su R(D)
D su R(D) termina in stato finale => N(R(D), R(D)) termina in stato non finale
N accetta L e (R(D),R(D)) non appartiene al linguaggio, D su R(D) non termina in stato finale entro 2^{2|R(D)|} dato che tcD(n)=2^2n, D su R(D) non termina in stato finale => assurdo
D su R(D) termina in stato non finale
N(R(D),R(D)) termina in stato finale
N MdT che accetta L, D su R(D) termina in stato final entro al più 2^{2|R(D)|} assurdo
Cos’è la classe NEXP?
{L linguaggio|esiste MdT M non.det. che accetta L t.c.
tcM(n)=O(2^n^k) per qualche k>=1}
Perché EXP ≠ NEXP ⇒ P ≠ NP?
Supp che P=NP allora Exp=NExp (contronominale)
Nexp sube Exp
Sia L in NExp, M mdt non.det. che accetta L in tcM(n)=O(2^n^k)
Costruisco ~L={x1^2^|x|^k| x in L} ovvero ho un prefisso stringa di L e serie di 1 non in L
Faccio vedere che ~L in NP
Sia N MDT non.det. per ~L
. dato y, controllo se esiste z:y=z1^2^|z|^k formattazione corretta
. eseguo M su z e in al più 2^|z|^k passi, decido se z in L oppure no
Complessità in tempo è polinomiale in n (lunghezza di y), quindi ~L in NP
Per hp, P=NP => ~L in P, facciamo vedere che L in Exp
- data x, costruisco stringa x1^2^|x|^k
- uso algoritmo polinomiale per ~L per stabilire se x1^2|x|^k in ~L
complessivamente è esponenziale
Qual è la relazione tra complessità in spazio e tempo?
Qual è la relazione tra complessità in tempo e spazio?
Cosa sono le classi PSpace e NPSpace?
Perché P ⊆ PSpace? (Dimostrazione – sono uguali?)
Perché PSpace ⊆ EXP? (Dimostrazione – sono uguali?)
Perché NP ⊆ PSpace? (Dimostrazione)
Qual è il Teorema di Savitch e il suo corollario? (Dimostrazione)
Perché PSpace = NPSpace?
Cosa significa che un problema è PSpace-difficile o PSpace-completo?
Se un problema PSpace-difficile è in P
allora vale P = PSpace?
Se è in NP
vale NP = PSpace? (Dimostrazione)
