7
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 1) I don't think general answers to these questions are possible; it depends on you. 2) Your way into computational complexity is probably the same as into any kind of mathematical topic: trial and error. 3) You ask three very different questions, which is not a good fit for this site. Please restrict yourself to one question at a time. $\endgroup$ – Raphael Aug 1 '16 at 23:02
  • $\begingroup$ Take a look to M.Sipser: "Introduction to the theory of computation"; it's more basic, but it is a great book. $\endgroup$ – Vor Aug 2 '16 at 18:08
  • 2
    $\begingroup$ suggest drop by Computer Science Chat periodically for tips/ encouragement etc. also think DWs recommendation below of online courses is spot-on, they are available, low-cost to free, and not dramatically different than the classroom experience, and some are taught by the very best authorities in the field, etc.; another angle is to study recent scientific papers... you dont mention your end goal however, do you want to get into CS as an academic? etc... yes there are conventions with CS proofs etc but they can be picked up over time, its not unlike mathematics culture which has its own conventions... $\endgroup$ – vzn Aug 4 '16 at 15:18
  • $\begingroup$ @vzn, I don't know 100% if I will get into theoretical CS as an academic or not. But probably, it will be computational complexity anyway or some topics the lie between the interplay of mathematical logic and complexity like descriptive complexity. $\endgroup$ – Fawzy Hegab Aug 5 '16 at 1:41
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ First of all, Thank you for the invaluable piece of advice. There is a course provided by MIT on algorithms and I will take it but it seems that most online courses and texts on algorithms deal with algorithms regarding sorting things and arrays which will be useful for data structures in programming later on not things that is relevant to mathematics or computational complexity (e.g. no mention of linear programming and simplex?) Do you think that such a course would still be important? for example, could you check please this online course by MIT and tell me if it will be useful to take it $\endgroup$ – Fawzy Hegab Aug 5 '16 at 1:46
  • $\begingroup$ Here is the link of the lectures of the course: youtube.com/playlist?list=PLUl4u3cNGP61Oq3tWYp6V_F-5jb5L2iHb .Is there any Textbook that you recommend to study algorithms? In MIT course, they use Cormen's text. What do you think? $\endgroup$ – Fawzy Hegab Aug 5 '16 at 1:47
  • $\begingroup$ I've found some courses on complexity theory. For example, there are about 10 lectures by Timoth Gowers on the web on complexity and quantum computation, I think they will be useful although his goal in complexity theory seems to be more towards lower bounds of circuits not introducing the topic for a novice but I think I can understand those lectures regarding complexity since I've already read the first few chapters of Arora and Barak text. $\endgroup$ – Fawzy Hegab Aug 5 '16 at 1:54
4
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ Thank you for the great advice. I wonder, How would category theory help me more? $\endgroup$ – Fawzy Hegab Aug 5 '16 at 1:57
  • $\begingroup$ I'm interested in that too, so I'll let you know when I find out! $\endgroup$ – m1cky22 Aug 5 '16 at 3:32
1
$\begingroup$

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.

$\endgroup$

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.