I am trying to get better in proofs and deep understanding of concept of computational complexity. Unfortunately, so far, with no success.

In order to get more intuition, I decided to do more exercises, but most of them are still difficult for me.

I am looking for exercises with solutions in field of computational complexity. Sometimes on course pages there are homeworks with solutions.

I am asking if you aware about any decent course on computational complexity with exercises and solutions on course page, please let me know.

  • $\begingroup$ Very good question! $\endgroup$ – Pratik Deoghare Dec 10 '12 at 18:38
  • $\begingroup$ If you happen to collect any exercises, consider adding them on exwiki.org $\endgroup$ – Jernej Dec 10 '12 at 20:32
  • $\begingroup$ Have you browsed the questions here, via complexity-theory? $\endgroup$ – Raphael Dec 11 '12 at 0:18

I had a course held by Jiri Srba a few years ago on basic complexity and computability theory is good, I would say. The second part (Lecture 9 to 15) goes through time and space complexity, shows some important results on the field and has pdf's of both exercises and solutions for each lecture. It is based on the book "Introduction to the Theory of Computation" by Michael Sipser, which also has a good walkthrough of both topics in general.

Link: https://intranet.cs.aau.dk/education/courses/2010/cc/course-plan/ (owned by Aalborg University)

Good luck!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.