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