Theory of Computational Complexity Autumn 2005 Friday 9:00 ~ 12:00 Electronic & Information Building  #219

last updated: 2005/12/08

 1. Objectives
 This course introduces Theory of Computational Complexity to the graduate students. As is known most of the real world problems do have subtle characteristics of appearing to be of same degree of complexity.  Students study Turing machine as a model for computers and its characteristics. The course contains different characteristics of decision and optimization problems and their important classification into P and NP. Students are taught how problems can be analyzed and proved to be NP-Complete in which case approximation algorithms are preferable. In addition students are given assignments for fine tuning and sharpening their skill with the theory of computational complexity.     By the end of the course, students will be able to:    learn various characteristics of problems and scientific way of formulating them.    learn how to analyze problems to resolve their complexity status.    For inherently difficult problems they also will learn how to devise approximation     algorithms for solving real world problems and  determine their performance     guarantee. .     Each student will be given a set of assignments to solve in order to improve his problem solving capability with regard to determining complexity status of problems and establish performance guarantee of approximation algorithms..   The course covers the following topics:   - Computers, complexity and intractability: problems, algorithms, complexity, polynomial time algorithms and intractable problems, provably intractable problems   - NP-complete problems, Theory of NP-Completeness:  Decision problems, languages, encodings, DTM and the class P, Non-deterministic computation and the class NP   The relationship between P and NP, Polynomial transformation and NP-Completeness   Cooks Theorem Proving NP-Completeness Results: six basic NP-Complete problems: 3-SATISFIABILITY, 3-DIMENSIONAL MATCHING  VERTEX COVER and CLIQUE, HAMILTONIAN CIRCUIT, PARTITION Some techniques for proving NP-Completeness: restriction, local replacement, component design   Using NP-Completeness to analyze problems, number problems and strong NP-Completeness NP-Hardness: Turing reducibility and NP-hard Problems Performance guarantee of approximation algorithms, applying NP-Completeness to Approximation problems Beyond NP-Completeness: structure of NP, polynomial hierarchy, complexity of enumeration problems Polynomial space completeness, logarithmic space, proofs of intractability and P vs NP List of NP-Complete problems: Graph Theory, Network Design, Sets and partitions Storage and Retrieval, Sequencing and Scheduling, Mathematical Programming Algebraic Number Theory, Games and Puzzles, Logic, Automata and language Theory, program optimization, Recapitulation and Open problems.

 2. Textbooks
 Overview of Theory of Computational Complexity: Recommended Book : Computer and Intractability: A Guide to Theory of NP-completeness Michael R. Garey/ David S Johnson WH Freeman and Company, 1979 Computational Complexity Theory (Ias/Park City Mathematics Series) by Steven Rudich (Editor), Avi Wigderson (Editor) Theory of Computational Complexity by Ding-Zhu Du, Ker-I Ko

 Midterm Final Assignment Total 30% 50% 20% 100%

 4. Instructor

Name 