2014
2014
Sei collegato come utente non registrato
Riepilogo dell'insegnamento: Computability and Computational Complexity
| Informazioni generali | |||
| Corso di Laurea | Informatica | Percorso | Computer Science and Technology |
|---|---|---|---|
| CFU | 6 | Università | TRENTO |
| Ore di didattica frontale per CFU | 8 | Settore Scientifico Disciplinare | MAT/01 |
6 cfu così ripartiti nelle aree:
- 6 CFU nell'area MAT - Crediti di MATEMATICA
Sillabo dell'insegnamento
- MAT - Crediti di MATEMATICA
-
MAT/01 - Logica Matematica
Alternating Computation: Alternating TMs. Class AP. -
MAT/01 - Logica Matematica
Interactive protocols, class IP. Shamir's theorem. Class AM (Arthur - Merlin). -
MAT/01 - Logica Matematica
Space complexity classes: LOGSPACE, NLOGSPACE, PSPACE, NPSPACE. Savitch's theorem. Complexity of logical languages and systems. Probabilistic complexity classes: BPP, RP, ZPP. -
MAT/01 - Logica Matematica
Time complexity classes. P and Edmonds-Cook-Karp's thesis. Problems in P. Class NP. Problem P = NP. NP-completeness. Cook's theorem on SAT. Problems NP-complete. Class co-NP, NP-intermediate problems. Polynomial hierarchy, class PH. -
MAT/01 - Logica Matematica
Measures of complexity, problems' classification. Complexity classes. Reductions. -
MAT/01 - Logica Matematica
Computability. Turing machines. Decidable languages, computable functions. The Halting Problem.
(*) Le sottoaree con asterisco sono quelle che il GRIN auspica facciano parte in via prioritaria dei sillabi degli insegnamenti assegnati all?area stessa
