Computational Complexity

[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) |

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

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.

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

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

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.

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.

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

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

**Reading****:
**[PAP] pp. 219-227.

**Reading****:
**[SIP] pp. 277-301.