New Page 1

Computational Complexity

Bibliography

[SIP]	Michael Sipser, Introduction to the Theory of Computation, PWS Publishing Company, 1997.
[PAP]	Christos H. Papadimitriou, Computational Complexity, Addison-Wesley Publishing Company, 1995.
[CLR]	Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introduction to Algorithms, The MIT Press, 1990. (Hebrew version available)

Grading Policy

Students must submit all home assignments, but 1, in due time, in order to take the final test!

One has to pass the final test in order to get a passing grade the course. Nevertheless, once one passed the final test (hopefully everyone does) the final grade in the course would be a waited average of the test and the two quizzes, where each quiz accounts for 15% of the grade (hence the test grade's accounts for 70% of the final grade).

Course Plan

Introduction

Intuitive description of the basic aspects of Computational Complexity Theory that will be covered in the course, including: Computational Problems Exponential-time algorithms Growth rate Tractability Reductions NP-completeness and the NP vs. P open question Approximation algorithms for NP-hard problems Space complexity.

Turing Machines

Motivation Schematic description Formal definition of deterministic Turing machine (DTM) The language accepted by a TM multitape Turing machines and equivalence with only a polynomial loss of efficiency to DTMs The Church-Turing thesis Pseudo-Codes and Turing machines

Reading: [SIP] pp. 125-140 (Turing machines).

Complexity Classes

Time and space deterministic/non-deterministic complexity classes Basic classes: P, EXPTIME, PSPACE, NP Complement classes Reductions Completeness Relations between complexity classes

Reading: [SIP] pp. 234--241 (P), 277-279 (Space complexity), 281-282 (PSPACE, EXPTIME).

The Cook-Levin Theorem

Satisfiability of propositional calculus formulas (SAT) is NP-Complete Representation of computations by tableaus Proof of the Cook-Levin theorem Using reductions to show NP-Completeness.

Reading: [SIP] pp. 254-259.

NP-Complete Problems

Basic propositional calculus definitions: CNF, DNF 3SAT Revised version of the Cook-Levin theorem: 3SAT is NP-Complete CLIQUE: description, non-deterministic algorithm, reduction from 3SAT INDEPENDENT-SET: description, non-deterministic algorithm, reduction from CLIQUE

Reading: [SIP] pp. 259-270.

On the Reasonability of Finding Paths in Graphs

Hamiltonian path (HAMPATH): definition, examples, NP-Completeness Eulerian path: definition, examples, the Euler theorem - polynomial time algorithm for Eulerian paths

Reading: [SIP] pp. 262-267 (Hamiltonian paths).

Approximation Algorithms

Motivation for Optimization problems. What is an approximation algorithm? Vertex-Cover (VC): definition, proof of hardness and approximation algorithm (factor 2), including demonstration and analysis Set-Cover (SC): definition and proof of hardness Greedy approximation algorithm: demonstration and two bounds on the approximation factor: an easy one of logn, and a tight one -though more complicated to proof - of lnn.

Reading: [CLR] pp. 523-524, 530-533.

The Traveling Salesman Problem - On Approximation and Its Limits

The Traveling Salesman Problem: (TSP): description, definition and examples Is the greedy strategy useful? Approximation algorithm (factor 2) for weight functions which satisfy the triangle inequality: specification, demonstration and analysis Hardness of approximation within any constant factor for the general case and the connection to gap problems.

Reading: [CLR] pp. 525-527.

coNP and Pratt's Theorem

coNP: definition Validity of propositional calculus formulas - an example of a coNP language On the connection to NP and complement languages coNP-Completeness P is a subset of coNP The NP=coNP? question and its connection to the P=NP? question Deciding if a number is prime (PRIMES) - another example for a coNP language Pseudo-polynomial algorithm for PRIMES Pratt's theorem: PRIMES is also in NP.