[Computational Complexity] But seriously now folks- what do you make of barri...
- In my April Fools Day Post I said the following:
Here are problems that I believe can be solved with current techniques.That was indeed true- since they were all known theorems. However, I was making a more serious point in capital letters. I will make it again here using all small letters.
in theoretical computer science we have some results on what techniques are not going to suffice to solve P vs NP and other problems. the authors of these results claim (correctly) that they are trying to get us to look at other techniques. however, proving barrier results can become an end in itself. what to the barrier results mean both mathematically and sociologically?
- has there every been, in the history of mathematics, an open problem that inspired so many negative results?
- one can argue that in logic there was work on negative result. however, before godel's inc. thm, was there the kind of flurry of activity to try to disprove hilbert's program could work that there is now on trying to prove that proving p \ne np is going to be hard. i do not think so. for ch there was more of this before cohen, but again, not as much as now.
- how about in number theory? i have never seen a result along the lines of the following techniques will not suffice to solve goldback's conjecture. are there any?
- why is P vs NP different than other problems in math? why have negative results about trying to prove it become a topic people work on?
- to be fair there aren't that many negative results, though they seem to be growing and are regarded (correctly) as important.
- the real question is will the barrier results lead to a prove that p is not np (or even that p is np though i find that unlikely).
- the other real question is, are these results being pursued because they are important or because we are in a rut and can't do much else. i tend to think its because they are important since (a) there is lots of non-barrier work in complexity also, and (b) barrier results are hard! it would be an odd way to get out of a rut by going into a really hard area. when i am in a rut i try to do things that are rather doable.
Posted By GASARCH to Computational Complexity at 4/07/2010 09:14:00 AM