Complexity Theory: A Modern Approach

http://www.cs.princeton.edu/theory/complexity/

by Rod • 17 years ago

20 12 17 years ago

cs.princeton.edu

barbie172• 17 years ago

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.

YuriNiyazov3• 17 years ago

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

barbie172• 17 years ago

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.

Rod• 17 years ago

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.

Herring• 17 years ago

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

nikete• 17 years ago

So thats your objective function.

YuriNiyazov3• 17 years ago

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?

bdr• 17 years ago

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

dantheman• 17 years ago

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

simplegeek2• 17 years ago

No TOC ;(

simplegeek2• 17 years ago

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

Complexity Theory: A Modern Approach

Related Stories