Complexity Theory
(Bridging Course - MCL)
School year 2007/2008
 

Lecturer:
 
 

Tutoring sessions: Prof. Doutor Carlos Viegas Damásio (cd@di.fct.unl.pt)

Course timetable:
   

Tutoring sessions: Wednesdays, 10:10 am - 11:00 am (232 EII)

Examination dates: 31st January and 21st February.


Mailing List: https://mail.di.fct.unl.pt/mailman/listinfo/mcl-ct (you can now subscribe the mailing list)

 

Date Summary Bibliography Readings/Exercises
Session 1 (2007/10/03) Presentation of tutor and students.

Bibliography.

 Adopted book:

[Sip] Michael Sipser. Introduction to the theory of computation. PWS Publishing Company, 1997.

Complementary readings:

[GJ] Garey & Johnson. Computers and Intractability (A guide to the theory of NP-completeness). Freeman and Company.

[PAP] Christos Papadimitriou. Computational Complexity.Addison-Wesley Publishing Company, 1995.

 

 Note: The readings necessary for each class are provided in this column. So, you should read them before coming to the session.

The complementary readings, are extra readings that can help in a deeper understanding of the subjects being discussed.
Session 2 (2007/10/10) Discussion of Chapter 1: Problems, Algorithms and Complexity. Polynomial algorithms and intractable problems.   Mandatory readings:
  • Chapter 1 of  Garey & Johnson
  • Chapter 1 of  Papadimitriou
Session 3 (2007/10/17) Turing Machines.
Variants of Turing Machines: multi-tape Turing machines and non-deterministic Turing machines.		   Mandatory readings:
  • Chapter 3 of [Sip]
Session 4 (2007/10/24) The P and NP classes.  

Mandatory readings:

  • Sections 7.1, 7.2 and 7.3 of  [Sip].

Complementary readings:

  • Chapter 2 of [PAP].
  • Pages 17-33 of [GJ].
Session 5 (2007/10/31) Polynomial time reducibility and NP-completeness.
The Cook-Levin Theorem.		  

Mandatory readings:

  • Sections 7.4 of  [Sip].

Complementary readings:

  • Chapter 4 and 8 of [PAP].
  • Pages 34-44 of [GJ].
Session 6 (2007/11/07) Important NP-complete problems: SAT, 3SAT, 3DM, VERTEX COVER, HC and PARTITION.  

Mandatory readings:

  • Section 7.5 of  [Sip].
  • Section 3.1 of [GJ].

Complementary readings:

  • Sections 9.1, 9.2 and 9.3 [PAP].
Session 7 (2007/11/14) Methods for proving NP-completeness results. The MINIMUM TEST COLLECTION and DOMINATING SET problems.  

Mandatory readings:

  • Section 7.5 of  [Sip].
  • Section 3.2 of [GJ].
Session 8 (2007/11/21)
Number problems and NP-strong completeness results		   Mandatory readings:
  • Section 9.4 of [PAP]

Complementary readings:

  • Chapter 4 of  Garey & Johnson

(2007/11/28)

No session this week

  

Exercises: Pages 75-76 of [GJ].
Session 9 (2007/12/05) Savitch's theorem, PSPACE and PSPACE-completeness.  

Mandatory readings:

  • Sections 8.1, 8.2 and 8.3 of  [Sip].

Complementary readings:

  • Section 9.1 of [PAP].
  • Sections 7.4 of [GJ].
Session 10 (2007/12/12) Complexity classes L and NL.  

Mandatory readings:

  • Sections 8.4, 8.5 and 8.6 of  [Sip].

Complementary readings:

  • Chapter 16 of [PAP].
  • Sections 7.5 of [GJ].
Session 11 (2007/12/19) Hierarchy theorems. NP-hardness  

Mandatory readings:

  • Chapter 9 of  [Sip].

Complementary readings:

  • Chapter 10 of [PAP].
  • Sections 5 of [GJ].
Session 12 (2008/01/09) Alternating machines, Polynomial Hierarchy and enumeration problems  

Mandatory readings:

  • Sections 10.3 of  [Sip].
  • Sections 7.1, 7.2 and 7.3 of [GJ]

Complementary readings:

  • Chapter 17 and 18 of [PAP].
Session 13 (2008/01/16) Approximation algorithms, probabilistic algorithms, interactive proofs and parallel computation.  

Mandatory readings:

  • Sections 10.1,10.2, 10.4 and 10.5 of  [Sip].

Complementary readings:

  • Chapter 6 of [GJ]
  • A lot of chapters of [PAP]...

 


(c) 2007 Carlos Viegas Damásio