Aim of the course

The course sets the theoretical bases for being able to discuss two fundamental properties of computational problems.

Given a problem, we will initially be concerned about its computability:

• Is there a method to solve the problem?
• Can we describe this method in an unequivocal way?
• Is there a universal “language” for such task?

When a problem is found out to be solvable, we can wonder how efficiently it can be done.

• What are the meaningful criteria to express how hard a problem is?
• Is there a meaningful way to classify problems with respect to their hardness?
• Does this classification tell us something about the limits of our capability to solve problems?

Prerequisites

Basic notions of mathematical logic

Expected outcome

At the end of the course, the students will be able to:

• Describe problems and problem instances in a formally precise way.
• Describe the solution of simple problems in terms of a universal computational model (the Turing Machine).
• Prove that a specific problem (Turing's halting problem) is not computable and recognize the importance of this result.
• Apply the formal notion of reduction in order to extend properties of known problems to new ones.
• Identify quantitative criteria to describe the complexity of an algorithm with respect to instance size.
• Describe the main time and space complexity classes, and their inclusion relationships.
• Define what it means for a problem to be complete for a class.
• Prove that a specific problem (SATISFIABILITY) is complete in the NP class (Cook's Theorem).
• Discuss the P vs. NP problem and its main implications on various branches of computer science.
• Analyze how extensions of the basic computing model (randomness, quantum computing) can benefit the solution of some problem classes.

Program outline

For the actual program, see below.

• Computability
  • Turing machines.
  • Decidable languages and computable functions.
  • The Halting Problem.
  • Other undecidable languages and uncomputable functions.
  • Rice's Theorem.
• Computational Complexity
  • Problem instance size, measures of complexity, classification of problems.
  • Time complexity classes: P, NP, EXP. NP-completeness. Study of NP-complete problems.
  • Space complexity classes: LOGSPACE, NLOGSPACE, PSPACE, NPSPACE. Savitch's theorem.
  • Polynomial hierarchy and canonical complete problems.
  • Advanced topics, depending on available time ((randomized classes, counting classes, interactive proofs, cryptography, quantum computation, approximation).

Textbooks

The following books may be useful, but none is mandatory. References to online material will be provided in the course program section.

Sanjeev Arora and Boaz Barak. Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN 9780521424264 [Draft of the book]

John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman. Introduction to Automata Theory, Languages and Computation. Pearson new International Edition, 2013. ISBN: 9781292039053

Christos H. Papadimitriou. Computational complexity. Addison Wesley (Pearson College Div.), 1994. ISBN 9780020153085