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.
Fermat's Last Theorem comes to mind, but often these results came in the form of someone saying "I HAVE A PROOF OF FLT!" when they didn't.
ReplyDeleteInfinite descent is not sufficient, nor is the method employed by Gabriel Lame (due to the fact that not all rings have unique factorization).
We need "barrier problems", no question. But when concentrating on P vs. NP and the like, we often forget that the real barriers of our understanding in complexity consist of much "simpler" problems. Like the following one:
ReplyDeleteFor a (0,1) matrix A, let t(A) be the smallest number t such that one can write A as a sum (over the reals) of t 0-1 matrices such that the 0-entries in each of these matrices can be covered by at most t all-0 their submatrices.
Easy counting shows that n-by-n 0-1 matrices A with t(A)>n^{1/2} exist.
Problem: Exhibit an EXPLICIT 0-1 matrix A with t(A)>n^c for an arbitrary small constant c>0.
Be it so “simply,” this is a more than 30 years old problem in computational complexity! Such a matrix would give us the first super-linear lower bound on the size of log-depth circuits. The first real progress in this field. This problem (and many similar combinatorial ones) sound much simpler. If we cannot solve such "simple" problems, what a solution of P vs. NP problem will give us? Especially, when we all "know" that P\neq NP. We will still be unable to solve these "simpler" problems.
P vs NP itself is a barriers result. If we prove P neq NP then everyone can stop looking for worst case NP algorithms.
ReplyDeleteIf we prove P neq NP then everyone can stop looking for worst case NP algorithms.
ReplyDeleteWill we then also know that the multiplication of two n-bit integers requires super-linear size circuits?
Galois's work and degree 5<= polynomials, impossibility of trisecting, impossibility of constructing third root of 2, unprovability of fifth axiom of Euclid from the rest of his axioms, undecidability of Diophantine equations, ... and of course Godel and Cohen's work, and also many infinite set theoretical statements.
ReplyDeleteI guess there are more. It seems that it has always been that there was a problem that people were interested in for some time and many tried to solve them, but at some point someone notices that there is the possibility that they are impossible to solve. Also the possibility of formalizing things is important, without formalization of what are the methods, we can not even express that these methods can not solve those problems preciously, let alone proving that the methods do not work.
If I was pessimistic, I would say that there is the possibility that ZFC+strong cardinal axioms can not decide P vs NP, and that even this is not provable in it, and so on forever ... but I am not. :)
Also these kind of result have been usually first state as some object does not exists, but later because of nonexistence of these objects we were able to prove/construct/discover other theorems/objects/algorithms.
ReplyDeleteAnon 5: Thanks for all of those examples.
ReplyDeleteFor 5th degree equation--- were they trying to show that there WAS such an equation and were trying to rule out approaches to it? I do not know.
In all of the examples the naysayers had it right. If P vs NP follows that pattern then we may have P = NP (which would shock
Lance Fortnow, but Richard Lipton wouldn't be too surprised.)
In physics, Richard Feynman set forth a barrier hypothesis in a 1982 article Simulating physics with computers, to the effect that "The full description of quantum mechanics, ... because it has too many variables, cannot be simulated with a normal computer" (emphasis Feynman's).
ReplyDeleteEver since 1982, Feynman's barrier has been dissolving; first slowly, but nowadays more quickly. For quantum chemists it is pretty much totally dissolved; for condensed matter physicists it is largely dissolved, and for quantum information theory physicists the dissolution of the barrier is just now getting underway.
The key has been to recognize that if we look at dynamics with the geometric and category-theoretic toolset of Mac Lane and Arnol'd, then quantum and classical dynamics don't look all that different. As for the large-dimension barrier that Feyman pointed-out, we can dissolve it for quantum systems via the same mechanism that molecular simulationists exploit in classical systems: the dynamical compression of trajectories.
Classical mechanics calls these compressive dynamical mechanisms "thermostats"; quantum dynamics calls them "Lindblad processes"; but this distinction is mathematically arbitrary, because when regarded from the Mac Lane/Arnol'd geometric/category-theoretic point-of-view they are seen to be mathematically the same mechanism.
In the practical world, we see that thermostats and Lindblad processes are ubiqutious ... in fact, we don't presently have any technology and/or experiments that provably probe the large-dimension barriers that Feynman discussed.
Similarly, with respect to P versus NP ... how often in the real world do we deal with problems that are NP-complete? Isn't there---in practice---always extra informatic structure available to solve real-world problems ... in the same way that thermostats and Lindblad processes are ubiquitously available to help us simulate dynamical systems?
Now, in complexity theory there *IS* one big exception: cryptography. And in quantum physics too there is one big exception: quantum computing. That is why the deepest mysteries of complexity theory and quantum mechanics are so often encountered in cryptographic and quantum computing settings.
----------
@article{Feynman:82, Author = {R. P. Feynman}, Journal = {International Journal of Theoretical Physics}, Number = {6--7}, Pages = {467--488}, Title = {Simulating physics with computers}, Volume = 21, Year = 1982}
I am not sure about degree 5<= polynomials, but my guess is that people were trying to find formulas for solving them. The reason for this is that as far as I remember Galois's work is considered revolutionary. The right place to ask this question is FOM mailing list:
ReplyDeletehttp://www.cs.nyu.edu/mailman/listinfo/fom/
Also it is a natural place to ask for more negative results.
ps: I searched their archive for Galois, did not find an answer.
If I recall the proof is that there is no general equation to give you the roots of a degree 5 polynomial.
ReplyDeleteHmmm ... yet another class of answers to GASARCH's question "What do you make of barrier results?" can be given using one of Dick Lipton's most useful phrases: "Barrier results are theorems about proof technology." In detail: "Barrier theorems assert that such-and-such a class of proof technology does not exist."
ReplyDeleteThis point-of-view enlarges the class of well-known barrier results to include examples like: "The only associative normed division algebra over the complex numbers are the complex numbers themselves" and "The only normed division algebras over the reals are the real numbers, the complex numbers, the quaternions, and the octonions."
These barrier theorems appear trivial to modern eyes ... yet they definitely were not trivial to (for example) William Hamilton's generation.
From this point of view, the text A=B contains innumerable examples of barrier result, relating specifically to the existence versus non-existence of broad classes of combinatoric identities.
Obviously, we are very far from understanding P=?=NP at this level ... we are only beginning to perceive even the obstructions to a straightforward proof ... and therefore you can count me as an enthusiast for every kind of barrier result. More please!
Hmmmm ... to state the previous result more provocatively: arguably it would be a disaster for complexity theory, if P≠NP were proved by some ingenious technical trick ... because we would have the proof without fully understanding the obstructions ... the latter task being (arguably) more important than the former.
ReplyDeleteThere is plenty of mathematical precedent for this point of view: Grothendieck was vastly dissatisfied with Deligne's proof of the Weil conjectures, for precisely this reason.
These considerations amount to saying that mathematics is largely about the understanding of barriers, and therefore, we need all the barrier results we can get.
This point-of-view seems very reasonable to me ... even though (obviously) it is not the whole story.
Look at Jeff Lagarias's paper about the 3n+1 conjecture and all the approaches to it that can't work.
ReplyDelete