automi dim

dim	tip
NFA $\equiv$ DFA	delta = E (insieme degli stati raggiunti da ogni stato nel set)
chiusure REG	unione nuovo stato con $ϵ$, intersezione prod cartesiano, concat quando arrivo a fine L1 $ϵ$ per $q_{02}$, star quando ho finito $ϵ$ arco verso l’inizio
reg $\equiv$ L(re) / regex	primo verso x induzione su casi regex, 2o verso NFA generalizzato + CONVERT(G’)
pumping lemma REG	ricordati s ⇐ p+1
DFA to CFG	Vq + Vq → aVp, $\varphi$ biiettiva x dimostrazione
Chomsky	ricorda S0 → S (poi $ϵ$ regole poi regole unitarie poi k>=3 poi xX)
CFL $⟺$ PDA	lato CFL: costruiamo PDA x grammatica G con qstart, qloop, qacc + 4 delta lato PDA: CFG con 3 regole claim Apq genera x iff porta P da p a q senza cambiare stack (x induzione)
pumping lemma CFL	cammino + lungo i genera stringhe max $2^{i-1}$; p = $2^m$; cammino$\ge m+1$; prendo ripetizione DAL BASSO x questo sottoalbero altezza massima m+1

dim	tip
NTM to TM	nastro 3 in ordine lunghezza + lessicogragico
Adfa, Anfa, Arex	Adfa simula, Anfa e Arex trasformano in DFA e NFA
Edfa, Ecfg	marca stati con archi entranti da marcati / marca var se ogni a dx marcata
Eqdfa	differenza simmetrica + Edfa
Acfg	max 2n-1 passi
linguaggi non rec	TM numerabili, stringhe infinite non numerabili, ogni linguaggio e’ una stringa infinita OR ! DEC = rec ^ coREC quindi non DEC → o L o $\bar{L}$ non rec (es. $\overline{ATM}$)
Atm non decidibile	costruisco D che fa M< M> e diagonalizza - che succede se faccio D< D> ?
DEC = REC ^ coREC	(1) se L DEC anche !L DEC (2) eseguo M1 e M2 in parallelo
A < B dec e B dec → A dec	decisore per A calcola f(w) e poi decide B
HALTtm non dec	x assurdo se HALTtm dec posso sapere se termina, ovvero decidere Atm (se termina simulo senno’ rifiuto)
Etm non dec	riduco ATM $\le \overline{E_{TM}}$ - se x $\ne$ w rifiuto, altrimenti simulo M(w)
REGtm non dec	riduco da ATM - se input nella forma 0n1n accetto senno’ simulo M(w)
$\Pi$ non puo’ essere valido e completo	altrimeti posso dimostrare “M(y) termina” e fare un decisore per HALTtm
G1 - non puo’ essere consistente e completo	${\varphi }_M$ = “M< M> termina”, $R_{\pi }$ diagonalizza - se $\varphi$ o $\neg \varphi$ dimostrabile $\Pi$ inconsistente
G2 - se consistente, non puo’ dimostrare “consistente”	prendo cose dim 1, assumo consistente e x modus ponens ottengo che dimostra $\neg prov(\varphi )\wedge \neg prov(\neg \varphi )$

dim	tip
PATH IN P	marco vertici con archi entranti
2COL in P	coloro i vertici e i loro vicini (x tutte le CC)
2SAT in P	rappresento $\varphi$ come grafo, x v y diventa le due →; $\varphi$ SAT $⟺$ nessuna CFC ha $x$ e $\bar{x}$ (SAT ⟶ ) (a,b) vuol dire a T - > b T, se c’e’ x ⟶ !x allora e’ necessario x F quindi non puo’ esserci !x ⟶ x (no x !x ⟶ ) ordinamento topolone; assegnamento “x = T se x appare dopo !x”; per nessun (a,b) si ha a = T e b = F quindi tutte impl vere quindi soddisfacibile grafo + Tarjan + controllo
3COL in verifierNP	rifiuta se stesso colore vicini
3SAT in NP	prova tutti gli ass in parallelo
verifierNP = NP	(1) se L verificatore polytime, il certificato è polinomiale - la NTM esegue il verificatore con ogni y in parallelo (2) se NTM, uso come certificato le scelte di N
A $\le$ B e B in P ⟶ A in P	faccio M_A = MB(riduzione(()))
4COL in SAT	$\varphi ij$ ha $\neg (x_i⟺x_i^{\prime }\wedge x_j⟺x_j^{\prime })$
3COL ⇐ 4COL	aggiungo un nodo e lo coloro diverrso
Cook-Levin (SAT in NP-COMPLETE)	tableau di computazione di N su un ramo ${\varphi }_{cell}\wedge {\varphi }_{start}\wedge {\varphi }_{move}\wedge {\varphi }_{acc}$ ricorda ${\varphi }_{cell}$ e’ almeno 1 colore + non 2 colori $O(n^{2k})$
3SAT ⇐ K-CLIQUE	RIDUZIONE trasformo $\varphi$ in un grafo - nodi tutti connessi tranne stessa formula e x !x + faccio iff
NP = coNP $⟺$ UNSAT in NP	unSAT in coNP=NP SAT NP-completo faccio !L $\le$ SAT $⟺$ L $\le$ UNSAT
spazio limita tempo	SPACE(f(n)) $\subseteq$ TIME(f(n))
tempo limita spazio	DTIME($2^{O(f(n))}$) $\subseteq$ SPACE(f(n))
PATH in SPACE(log^2 n)	divide et impera, in ogni chiamata solo indici log bit
Savitch NSPACE(f(n)) $\subseteq$ DTIME($f^2(n)$)	wlog 1 conf accettante, PATHG genera grafo al volo, TM esegue PATHG e costa spazio O($f^2(n)$)
PATH NL-completo	(sappiamo PATH NL-hard perche’ abbiamo visto savitch) mi segno currNode
THT siano t1 << t2 esiste L DTIME(t2) ma non DTIME(t1)	simulo con “timer” t1.5 passi e ritorno l’opposto - diagonalizzo per t1
SHT s1 e s2 O(s1)	simulo in spazio limitato e in timer con max 2^O(s2(n))

DIMOSTRAZIONI UGUALI

• ”marco vertice che ha archi entranti da vertice già marcato” style