Complexity Theory

Università degli Studi di Udine
Anno Accademico 2017-2018


During this course we intend to present the main results in the field of computational complexity of algorithms. In particular, we intend to discuss the classical hierarchy of complexity classes and the main techniques for the analysis of related problems. We will also present basic ideas and notions of some interesting innovative computational models recently proposed in the scientific community.

See Prof. Alberto Policriti's web pages for Advanced Algorithms.


  1. Computational classes. Hierarchy theorem. Gap theorem. Savitch theorem. Immermann-Szelepscenyi theorem and consequences. Computational reductions and completeness. Classes outside NP.
  2. Algorithms. The problem of automata minimization and the notion of bisimulation. Hopcroft algorithm. Paige-Tarjan algorithm. Paige-Tarjan-Bonic algorithm. The notion of simulation. Symbolic data structures.
  3. DNA Computing. Adleman and Lipton model. Solutions for SAT and other NP-complete problems. Universal Turing machine in DNA computing.
  4. To be decided (e.g., Approximation Algorithms, Parallel Computations, Hybrid Automata).


The exam is oral on appointment. In agreement with the teacher, part of the exam can consist of a presentation on a selected project.


  1. C. H. Papadimitriou. Computational Complexity. Addison Wesley. 1995
  2. P vs NP
    1. A Short History of Computational Complexity by L. Fortnow and S. Homer
    2. The History and Status of the P versus NP Question by M. Sipser
    3. Computability and Complexity by Neil Immerman
  3. PSPACE-completeness
    1. Word Problems Requiring Exponential Time by L. J. Stockmeyer and A. R. Meyer
  4. Bisimulation and Automata Minimization
    1. Computing in Non Standard Set Theories by C. Piazza
    2. An NlogN Algorithm for Minimizing States in a Finite Automaton by J. Hopcroft
    3. CCS Expressions, Finite State Processes, and Three Problems of Equivalence by P.C. Kanellakis and S.A. Smolka
    4. Three Partition Refinement Algorithms by R. Paige and R. E. Tarjan
  5. OBDD
    1. Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams by R. E. Bryant
    2. Graph Algorithms for Massive Data-Sets by R. Gentilini
    3. Symbolic Model Checking by K. McMillan
  6. Automi Ibridi
    1. Corso su Automi Ibridi by C. Piazza
  7. DNA Computing
    1. Molecular Computation of Solutions of Combinatorial Problems by L. Adleman
    2. Speeding up Computations via Molecular Biology by R. Lipton
    3. On the Computational Power of DNA by D. Boneh, C. DunWorth and R. Lipton
    4. A DNA and restriction enzyme implementation of Turing Machines by P. Rothemund
    5. A Survey on DNA Computing by N. Pisanti
  8. Quantum Computing
    1. Machines, Logic and Quantum Physiscs by D. Deutsch, A. Ekert, and R. Lupacchini
    2. Quantum Computing by A. Hagar and M. Cuffaro