# CS 764 Computational Complexity

## Objectives

To give the student further exposure to the classification of problems based
on their computational requirements, and to mathematical tools designed to explore
the structural consequences of such classifications.

Students are expected to have basic knowledge of complexity theory (P, NP,
NP-completeness).

## References

References to be determined.

## Schedule

Three hours of lecture per week.

## Outline

### Structural Complexity (18 hrs)

Relativization. Structure of NP. Alternation and the polynomial-time hierarchy.
Interactive proof systems. Provably intractable problems. Feasible parallel
computations, Boolean circuits, and the class NC.

### Parameterized Complexity (9 hrs)

Fixed-parameter tractability. Kernelization and bounded search trees. Relationship
to optimization problems and approximation schemes. Parameterized reducibility
and W[1]-completeness. The W-hierarchy.

### Kolmogorov Complexity (9 hrs)

Randomness and incompressibility. Robustness. Algorithmic complexity and algorithmic
prefix complexity. Applications to computational complexity.