Presentazioni PowerPoint di Complessità

Presentazioni redatte da Muli Safra per un corso in Complessità Computazionale

  1. introduzione alla Complessità Computazionale
  2. macchine di Turing
  3. ridurre un problema ad un altro
  4. il teorema di Cook
  5. problemi NP-completi
  6. camminini e circuiti Hamiltoniani
  7. 2SAT e MAX-2SAT
  8. quando la risorsa è lo spazio
  9. la gerarchia polinompiale e BPP
  10. algoritmi approssimati
  11. il problema del commesso viaggiatore
  12. la teoria PCP
  13. random walks
  14. crittografia
  15. zero knowledge proofs
  16. coNP; PRIMES è in coNP
  17. PRIMES è in P

created:   3 aprile 2003
updated:   3 aprile 2003 		© Department of Computer Science
University of Verona