Welcome to Introduction to Computational Complexity homepage
Course DescriptionIn this course we will study the basics of feasible computation and its limitations. Among the topics we will see:
- The classes P and NP.
- NP complete problems.
- Approximation algorithm, and hardness of approximation.
- Space bounded computation.
- Randomized algorithms and computational classes.
- Interactive proofs.
|Wednesday||12:00-14:00||Building 32, Room 209|
|Name||Web page||Office||Office hours|
|Ofer Neiman||http://www.cs.bgu.ac.il/~neimano||neimano at cs dot bgu dot ac dot il||Building 37, Room 215||Wed. 10-12|
- S. Arora, B. Barak. Complexity Theory: A Modern Approach., Cambridge University Press, 2009.
- M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
- C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
- J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computations. Second Edition, 2001.
- M.R. Garey and D.S. Johnson. Computers and Intractability, a guide to NP-completeness. 1979.
Grading PolicyFinal exam, 80%. Students MUST PASS the exam to pass the course.
The exam is with no supplementary material.
Homework assignments, 20%. There will be about 5-6 short homework assignments. These assignments do not include any programming.
There will be only one exam in the course (no MOED B).
You may hand in the exercises either by yourself or with one other student. Students whose partner has a valid reason not to hand in some assignment must still hand in the assignment. You may not hand in the assignments in groups larger than two. Cheating will not be tolerated. Cases of suspected cheating may result in the grade 0 on assignments and will be processed by the university disciplinary committee.