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.