|
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.
| 