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 NPComplete 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
 NPcomplete problems, Theory of NPCompleteness: Decision problems, languages, encodings, DTM and the class P, Nondeterministic computation and the class NP The relationship between P and NP, Polynomial transformation and NPCompleteness
Cook’s Theorem
Proving NPCompleteness Results: six basic NPComplete problems: 3SATISFIABILITY, 3DIMENSIONAL MATCHING VERTEX COVER and CLIQUE, HAMILTONIAN CIRCUIT, PARTITION
Some techniques for proving NPCompleteness: restriction, local replacement, component design
Using NPCompleteness to analyze problems, number problems and strong NPCompleteness
NPHardness: Turing reducibility and NPhard Problems
Performance guarantee of approximation algorithms, applying NPCompleteness to Approximation problems
Beyond NPCompleteness: structure of NP, polynomial hierarchy, complexity of enumeration problems
Polynomial space completeness, logarithmic space, proofs of intractability and P vs NP
List of NPComplete 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.
