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:
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?
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?
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.