[Computational Complexity] But seriously now folks- what do you make of barri...

Expand Messages

GASARCH

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

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.