Complexity Theory: A Modern Approach | Hacker News Reader

Complexity Theory: A Modern Approach

cs.princeton.edu

20 pointsRod12 comments

I would argue that for most entrepreneurs studying machine learning has greater marginal utility than studying complexity theory, but to each his/her own I guess.

Depends what your niche is. Do you manage a petabyte cluster? All of a sudden, everything that used to be "complexity theory" becomes "complexity practice".

No, I don't think we are talking about the same kind of complexity here. Complexity Theory is exactly the opposite of real world pragmatism. It is about the asymptotic behaviors of algorithms and the resources need to solve certain class of problems such as Traveling Salesman or Min-Set-Cover.

Actually, that is exactly what I am talking about. The implication was that problems like that do show up in "real-life" coding, and while brute-force solutions for those problems work for very small n, you need to recognize the fact that those problems do not have reasonable solutions in general, and you should know how to approximate the solutions (in the technical sense of "approximation"), and furthermore know enough complexity theory to know the situations where even an approximation will not have a reasonable solution.

For example, I believe that the problem of creating optimal schedules for high school students is NP-Complete (optimal in the sense that it will satisfy all of the students' preferences for electives, and all of the teachers' preferences for the classes they want to teach).

Yes, I admit that the example will never involve petabytes of data. That doesn't invalidate my original point though.

I certainly do agree that for most entrepreneurs machine learning is much more useful than computational complexity theory. However, I figured there might be some people on HN who would like to learn a bit more about complexity, and hence I submitted the URL, not because it's extremely useful, but because it's very interesting.

Life's too important to spend fixated on marginal utility.

So thats your objective function.

Just as I am reviewing Sipser, this shows up. On that note - is anyone on HN interested in creating a CS theory online study group? You see, I've had an interest in the "important, hard problems" of our field for a very long time now: both the "is P == NP ?" and "How do you make something people want?", but in this post I'd like to address the first one. I used to toy with the idea of going to grad school, becoming a hermit, and just studying complexity theory for the next 10 years, but since then I've become somewhat disenchanted with the allure of grad school. However, I still want to know what is wrong with all the purported proofs listed here:

http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

What do you guys think?

I have been wanting to work through the problems in OP. Doing it as part of a group might be helpful.

I'm not a member of this group, but it might be up your alley; http://people.csail.mit.edu/bjuba/crypto-complexity/

No TOC ;(

Here we go, http://www.cs.princeton.edu/theory/index.php/Compbook/Draft

Reply on news.ycombinator.com