MODULO DI COMPLESSITÀ (a
cura del Dott. Salvatore Cristofaro)
Notazioni asintotiche
Macchine di Turing e loro formalizzazione
Funzioni numeriche (Turing) computabili
Macchine di Turing multi-nastro
Relazioni tra macchine di Turing e macchine di Turing
multi-nastro
Classi di complessità temporale
La classe NP
NP-completezza
Il problema della soddisfacibilità proposizionale
(SAT)
Teorema di Cook
Catalogo di problemi NP-completi (3-SAT,
n-SAT, VertexCover, CLIQUE,
IndependentSet,
HamiltonianPath,
HamiltonianCircuit,
LongestSimplePath,
SetCover,
HittingSet,
SubgraphIsomorphism,
TravelingSalesman,
3-DimensionalMatching,
Partition,
SubsetSum,
Knapsack)
Complessità spaziale delle macchine di Turing
link alla dispensa
(Agg. 16/06/11)
|
|