Header image

Graduate Course
Summer 2009
Northeastern University
line decor
  NEU-RTES Laboratory  ::  
line decor
   
 
COURSE INTRODUCTION

This is a five day graduate course given at Northeastern University in Shenyang, China.
The invited lecturer is Martin Stigge. He is a PhD student of Division of Computer Systems, Department of Information Technology, Uppsala University, Sweden.
Target course takers are teachers, PhD students, and Master students of College of Information Science and Engineering, Northeastern University, China.
TIME & ROOM

July 13    10:00 - 12:00, 16:30 - 18:30
July 14    10:00 - 12:00, 16:30 - 18:30
July 15    10:00 - 12:00, 16:30 - 18:30
July 16    10:00 - 12:00, 16:30 - 18:30
July 17    10:00 - 12:00, 16:30 - 18:30

Rm 301, Zhulou Building
COURSE PAGE
http://www.it.uu.se/katalog/marst984/cc-st09
http://www.neu-rtes.org/courses/summer2009/              (local site for service)
PRELIMINARY COURSE OUTLINE

1st day (2009-07-13) - Introduction to Computability Theory

  • Math preliminaries, Problems as languages, Landau Symbols
  • Turing machines, decidability, non-determinism
  • Turing reductions, halting problem

2nd day (2009-07-14) - Complexity classes

  • Time and space complexity
  • Reductions, hardness, completeness
  • Non-determinism

3rd day (2009-07-15) - Polynomial Complexity

  • Inside P
  • NP, NP-complete
  • SAT, NodeCover, Clique, KnapSack, MultiprocessorScheduling, ...

4th day (2009-07-16) - The P-vs-NP Problem

  • The problems GI and PRIMES
  • Oracles, Polynomial time hierarchy
  • Relativization

5th day (2009-07-17) - Other complexity concepts

  • Non-uniform complexity: Circuits
  • Interactive Proof Systems
  • Probabilistic complexity classes

In the end of every day, the students will be given a couple of small problems to solve, for deepening the understanding of the day's lectures.
LITERATURE

The Lecture Notes of this course is available now!  (Download in PDF)
Course slides in PDF

Further Readings:

  1. Introduction to the Theory of Complexity, Daniel Pierre Bovet and Pierluigi Crescenzi, Prentice Hall
  2. Computational Complexity, Christos H. Papadimitriou, Addison Wesley

(Note that access to the above books is not a prerequisite.)
INFORMATION ANNOUCEMENT

Were there any change on lecture time and place, we will make announcements in class, via emails, or on the course web sites.

Course introduction in PDF

A list of course takers
CONTACT PERSONS
Mingsong Lv (吕鸣松)
mingsong@research.neu.edu.cn
138-4028-9915
Rm 404, Zhulou Building

Nan Guan (关楠)
guannan0609@hotmail.com
150-4036-4096
Rm 404, Zhulou Building
 
 
Last updated July 2009. For any questions on the website, please contact the webmaster