Topic

No. of hours

Lecture

Tutorial/Practical

Introduction :-

What Is Complexity Theory?

Didactic Background.

Overview.

Additional Literature.

3

3

-

Algorithmic Problems & Their Complexity :-

What Are Algorithmic Problems?

Some Important Algorithmic Problems.

Measuring Computation Time.

The Complexity of Algorithmic Problems.

3

3

-

Fundamental Complexity Classes :-

 The Special Role of Polynomial Computation Time.

Randomized Algorithms.

The Fundamental Complexity Classes for Algorithmic Problems.

The Fundamental Complexity Classes for Decision Problems.

Non-determinism as a Special Case of Randomization.

3

3

-

Reductions – Algorithmic Relationships: Between Problems.

When Are Two Problems Algorithmically Similar?

Reductions Between Various Variants of a Problem.

Reductions Between Related Problems.

Reductions Between Unrelated Problems.

The Special Role of Polynomial Reductions.

3

3

-

The Theory of NP-Completeness :-

Fundamental Considerations.

Problems in NP.  

Alternative Characterizations of NP.

Cook's Theorem.

3

3

-

NP-complete and NP-equivalent Problems :-

Fundamental Considerations.

Traveling Salesperson Problems.

Knapsack Problems.

Partitioning and Scheduling Problems.

Clique Problems.

Team Building Problems.

Championship Problems.

3

3

-

The Complexity Analysis of Problems : -

The Dividing Line Between Easy and Hard .  Pseudo-polynomial Algorithms and Strong NP-completeness.

An Overview of the NP-completeness Proofs Considered.

3

3

-

The Complexity of Approximation Problems – Classical :-

Results.

Complexity Classes.

Approximation Algorithms.

The Gap Technique.

Approximation-Preserving Reductions.

Complete Approximation Problems.

3

3

-

The Complexity of Black Box Problems :-

Black Box Optimization.

Yao's Minimax Principle.

Lower Bounds for Black Box Complexity.

3

3

-

Additional Complexity Classes :-

Fundamental Considerations.

Complexity Classes Within NP and co-NP.

Oracle Classes.

The Polynomial Hierarchy.

BPP, NP, and the Polynomial Hierarchy.

3

3

-

Interactive Proofs :-

Fundamental Considerations.

Interactive Proof Systems.

Regarding the Complexity of Graph Isomorphism Problems.

Zero-Knowledge Proofs.

3

3

-

The PCP Theorem and the Complexity of Approximation :-

Problems.

Randomized Verification of Proofs.

The PCP Theorem.

The PCP Theorem and In-approximability Results.

The PCP Theorem and APX-Completeness.

3

3

-