TOP

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

 

3. Grading Police

Midterm

Final

Assignment

Total

30%

50%

20%

100%

 

4. Instructor

Name

Mohammad Kaykobad (Bangladesh)

Contact Information

Tehephone : 031-201-2493
E-mail :

mkbd@oslab.khu.ac.kr

or kaykobad@gmail.com

Office :

Electronic & Information Bld. #B08

(Multimedia Laboratory)

    

5. Tentative Schedule

#

Date

(month/day)

Topic

Material

1

9/9

Computers, complexity and intractability:  problems, algorithms, complexity

DOC

2

9/16

Polynomial Time algorithms and intractable problems, provably intractable problems

DOC

3

9/23

NP-Complete problems, Theory of NP-Completeness: decision problems, languages, encodings, DTM and the class P, Non-deterministic computation and the class NP

DOC

4

9/30

The relation between P and NP Polynomial transformation and NP-Completenesss

DOC

5

10/7

Cook’s Theorem

DOC

6

 

Proving NP-Completeness results: Six Basic NP-Complete problems: 3-SATISFIABILITY, 3-DIMENSIONAL MATCHING

 

7

10/14

Colloquium I

NP-Completeness of a scheduling problem

ABOUT

PPT(11/21)

8

10/21

VERTEX COVER, CLIQUE, HAMILTONIAN CIRCUIT, PARTITION

DOC

9

10/28

NP-Completeness

DOC

10

 

Using NP-Completeness to analyze problems, number problems and strong NP-Completeness

 

11

11/4

Colloquium II

Complexities of some interesting problems in spanning trees

PPT

12

11/11

NP-Hardness: Turing Reducibility and NP-Hard problems

DOC

13

11/18

Coping with NP-Complete problems: performance guarantee of approximation algorithms, applying NP-Completeness to Approximation problems

DOC

14

11/25

Colloquium III

Some important problems and their complexity status

PPT

15

11/25

Beyond NP-Completeness: structure of NP, polynomial hierarchy, complexity of enumeration problems, polynomial space completeness logarithmic space, proofs of intractability and P vs NP

 

16

12/2

List of NP-Complete problems: Graph theory, Network Design, Sets and partitions, stirage and retrieval, sequencing and Scheduling, Mathematical programming

-

17

12/6

List of NP-Complete Problems: Algebraic Number Theory, Games and Puzzles, Logic, Automata and language Theory, program Optimization

 

18

12/9

Ramsey Theory and Recapitulation of the course material and Open problems

 

19

12/13

FINAL EXAM

-

 topicon.gif