Teoria
1
Definizione Informale di macchina di Turing
2
Definizione Formale di macchina di Turing
3
Macchine di Turing Non-Deterministiche
4
Linguaggi riconoscibili
5
Linguaggi decidibili
6
Codifica di un problema decisionale x
- Proprietà di chiusura dei linguaggi
7
Tesi di Church-Turing
8
$Mapping-Reduction$
9
Definizione linguaggio
10
Definizione proprietà di linguaggio
11
Definizione proprietà di linguaggio non triviale
12
Teorema di Rice
13
Complessità di tempo e notazione asintotica
- Definizione di Big-O notation
14
La classe $P$
15
La classe $EXP$
16
Complessità di Tempo di una TM Non-Deterministica
17
tLa classe $NP$