An advice to a self-learner of computational complexity

Question

I'm a mathematics undergraduate student (going to start my third year very soon). I'm trying to teach myself computational complexity. Sadly, there are no courses provided in my university on the topic and there are no specialists on it (In fact, it seems that my university has no specialists in theoretical CS at all). So, I have no choice to learn the topic except via self-study. I've already gone through the first few chapters of Computational complexity: A modern approach [ but I did not solve any of the exercises (except two or three in the first chapter exposing what are TM's and Halting problem) ]

I face some problems with the exercises of in the text:

1. one thing is that I feel that the kind of thinking needed in computational complexity is quite different than that of mathematics that I'm familiar with (There is an emphasize on algorithmic thinking etc and how to reduce problems to other problems and to make a TM simulating another TM etc) which is something I find difficult.

   Is there any way do you recommend to help me developing this level of maturity about algorithms, reductions etc?

2. One reason of difficulty of "1" is that I don't know to what extent should I be rigorous? For example, when I'm doing a reduction or a simulation, it's possible that I can see intuitively that something is clear and can be done but the details would be very very tedious to actually carry out and hence I feel that I don't understand the thing very well. The point is that, I know that there must be a compromise between rigor and intuitive thinking. But since I've no guide nor an instructor, I don't know where this line should be.

   when should I carry out all the details if something somehow clear and when should I be satisfied with the intuition? It seems that there are much more details in computational complexity than is usually present in the math I know and hence, where the compromise should be?

3. I wonder if there exists any source of exercises\problems that are quite easier than those provided in Computational complexity: A modern approach so that I can train myself with the basic notions\constructions etc before tackling more complicated exercises. Also, a source of (quite-detailed) proofs of the main theorems would be great since many theorems have only a sketch of the proof in the text.

For my background, I've learned basics of programming (I've trained for awhile in python, C and C++) but not much but I'm quite familiar with mathematics specially mathematical logic (up to completeness and Incompleteness theorems), advanced set theory (forcing), Algebra (linear, Abstract, universal algebra and some category theory) and basics of topology and reals analysis. I've taken a course on Discrete mathematics too (combinatorics + graph theory).

I apologise if my question is off-topic but I know no better place to propose those question than here.

Answer 1

My recommendation is to focus on two things: prerequisites, and practice.

Prerequisites: It's going to be harder to learn computational complexity without first having a good understanding of algorithms. At many schools, a class in algorithms is a prerequisite to the class on computational complexity. You mention you feel you may lack maturity in algorithms, and in your position, who wouldn't? It's a non-trivial subject that you haven't studied. So, my first piece of advice is: before spending too much time on computational complexity, first spend some time studying algorithms. There are many good algorithms textbooks and online courses (e.g., via Udacity, Coursera, or EdX). It might be helpful to spend some time learning that material. You don't need to learn every algorithm in the world, but try to get a feel for some common algorithmic techniques; designing reductions is basically designing an algorithm, so this knowledge will be helpful. Also, make especially sure you are comfortable with proofs of correctness for algorithms and asymptotic running time analysis.

Next, practice. No one starts out with a maturity with reductions. The way to get more comfortable with that is to practice -- do exercises until you either feel comfortable with the material, or the exercises uncover some gap in your understanding (which you can then go back and focus on learning more about). You probably can't learn the material without this kind of practice.

To help you practice, it may be helpful to look for an online course (a MOOC) on computational complexity. You can check Udacity, Coursera, or EdX.

How rigorous should you be? Rigorous enough that you are convinced that you could fill in all the details if you needed to (and that a fellow classmate at a similar level of studies could fill in all the details without thinking hard -- they'd agree filling in the details is tedious but straightforward and obvious).

Answer 2

Given that I'm the opposite (studying computer science/engineering, self studying math) I think I can shed some light on some topics.

I've recently taken an algorithms and complexity theory course that covered algorithms, formal languages, and complexity theory. I think all 3 will be very important if you want to really understand what you're doing. For example, if you don't understand big-O implications and how to analyze runtimes, you won't really understand what P and NP represent and it'll be harder to move into other complexity classes. If you don't understand TMs, automatas, etc., then you won't understand regular languages, CFGs, and what decidable and recursively enumerable languages represent. So my suggestions will stem from connections I've made to mathematics from computer science.

1. You've taken set theory and real analysis. You should be familiar with induction from most of your courses (a tool that was the most challenging part of algorithm analysis for many classmates) and recursion will most likely come naturally to you. When it comes to more abstract objects, while not directly related, I think a strong basis in abstract algebra (and anything further) will prove to be a huge advantage that you have. Groups, rings, etc., are algebraic objects that contain some structure and you have maps and morphisms between them. Turing Machines and automata are computational structures that contain some structure and rules and have transformations between them (Thompson's construction for regular expressions into NFAs, multi-tape TM's into a single tape TM). While general programming logic could be beneficial for understanding logic of TMs, category theory might help you out more.

2. I'm not sure what specifically you're asking, but if you can be rigorous, do it. There are some techniques used in mathematics that are used in many constructions (real analysis using epsilon delta proofs that build up to calculus from simple concepts) and there are techniques used in complexity theory (reductions from a problem to another, think of an injective map where you have to provide the map as opposed to proving it is injective).

3. This course (https://courses.engr.illinois.edu/cs374/lectures.html) provides lecture notes and slides and has great introductory reference materials. In no way does this cover everything, but it could be a great start for you. The lab work is pretty nice to look at and test your understanding, but often times it's more difficult than the required knowledge.

Lastly, your discrete maths will be of great help throughout all this. You'll see how important graph theory is in algorithm analysis and design as well as combinatorics for data structure analysis. Good luck and I hope you find what you're looking for!

Answer 3

I would suggest you (a) determine what prerequisite math you need, (b) stick to really understanding and going through the first 3-4 problems or so in each chapter, trust me even if those take long, you will get the hang of it then pretty quickly with future problems.