Contents (hide)

Welcome to Introduction to Computational Complexity homepage

Course Description

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

Course Schedule

Day Time Room
Wednesday12:00-14:00Building 97, Room 204


Name Web page E-mail Office Office hours
Ofer Neiman neimano at cs dot bgu dot ac dot il Building 37, Room 215 Wed. 10-12


  1. S. Arora, B. Barak. Complexity Theory: A Modern Approach., Cambridge University Press, 2009.

Other Textbooks

  1. M. Sipser. Introduction to the Theory of Computation. PWS Publishing Company, 1997.
  2. C. H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
  3. J. E. Hopcroft, R. Motwani, and J. D. Ullman. Introduction to Automata Theory, Languages, and Computations. Second Edition, 2001.
  4. M.R. Garey and D.S. Johnson. Computers and Intractability, a guide to NP-completeness. 1979.

Grading Policy

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