Complexity Theory for Simpletons
in [Theory]
|
Prev: HEAP SORT
Next: Greedy Algorithm
From: Craig Feinstein on 12 Mar 2006 20:41 Hi, I am interested in feedback on a paper I wrote here: http://arxiv.org/abs/cs.CC/0507008 entitled "Complexity Theory for Simpletons". It was written for a mathematically-literate audience, although not necessarily mathematicians or computer scientists. First of all, I want to know if readers think the paper is interesting and well-written. Second of all, I want to know if readers believe the claims of the paper and what they think of my explanations. There are three major claims of the paper: 1) P != NP and it is not difficult to prove such by showing by induction that a certain algorithm discovered in 1974 for solving the NP-complete subset-sum problem has the best running-time of all algorithms which solve subset-sum. (No one has ever beat this algorithm for solving subset-sum.) The algorithm was presented to me on usenet a few years ago. 2) The Collatz Conjecture is unprovable, if it is true. 3) The Riemann Hypothesis is unprovable, if it is true. Explanations for 2) and 3) don't use any Godel-like arguments; they just argue that any proof of these conjectures must have an infinite number of lines. The basic theme of the paper is that advanced mathematics is too hard for mortal human beings to understand. Craig
From: Jamie Andrews; real address @ bottom of message on 23 Mar 2006 15:13 Craig Feinstein <cafeinst(a)msn.com> wrote: > First of all, I want to know if readers think the paper is interesting > and well-written. Yes to both. You are good at writing grammatically correct sentences and paragraphs, which is much more than I can say for many people. Your mathematical exposition is not perfect, but your writing is easy to read. > Second of all, I want to know if readers believe the claims of the > paper and what they think of my explanations. There are three major > claims of the paper: > 1) P != NP and it is not difficult to prove such by showing by > induction that a certain algorithm discovered in 1974 for solving the > NP-complete subset-sum problem has the best running-time of all > algorithms which solve subset-sum. (No one has ever beat this algorithm > for solving subset-sum.) The algorithm was presented to me on usenet a > few years ago. Your fallacy here seems to be in assuming that the way the "meet-in-the-middle" algorithm decomposes the problem is the *only* way to decompose the problem. It could be that *if* the way it decomposes the problem were the only way to do it, then that algorithm would be the fastest. However, other algorithms for NP-complete problems use completely different approaches to decomposition. > 2) The Collatz Conjecture is unprovable, if it is true. Here the problem seems to lie in the statement "any proof of the Collatz conjecture must specify vector (x_0, x_1, ..., x_B)". The statement that the "proof must specify" the vector is vague and I don't think it can be made more precise. > 3) The Riemann Hypothesis is unprovable, if it is true. I didn't check this one because I can't remember what I learned before about the RH. But there may be a similar problem. As a meta-note, I think the reason that your post was not responded to for over 10 days may be that it seems very unlikely that someone could solve 3 of the most famous unsolved problems in math/CS in a relatively informal, 11-page paper with a lot of introductory exposition. There have been examples of "outsiders" solving important problems, the most famous possibly being Paul Cohen, who proved the independence of the continuum hypothesis. But IIRC, even Cohen was a trained mathematician; it's just that his training was not in the sub-area of mathematical logic. Your overall problem, IMHO, is that you don't write about the mathematical concepts with the extremely high degree of precision that is necessary to carry out convincing proofs. --Jamie. (Celebrating (?) 20 years on Usenet!) andrews .uwo } Merge these two lines to obtain my e-mail address. @csd .ca } (Unsolicited "bulk" e-mail costs everyone.)
From: Craig Feinstein on 24 Mar 2006 15:54 Jamie Andrews; real address @ bottom of message wrote: > Craig Feinstein <cafeinst(a)msn.com> wrote: > > First of all, I want to know if readers think the paper is interesting > > and well-written. > > Yes to both. You are good at writing grammatically correct > sentences and paragraphs, which is much more than I can say for > many people. Your mathematical exposition is not perfect, but > your writing is easy to read. Thank you. I'm glad. > > > Second of all, I want to know if readers believe the claims of the > > paper and what they think of my explanations. There are three major > > claims of the paper: > > > 1) P != NP and it is not difficult to prove such by showing by > > induction that a certain algorithm discovered in 1974 for solving the > > NP-complete subset-sum problem has the best running-time of all > > algorithms which solve subset-sum. (No one has ever beat this algorithm > > for solving subset-sum.) The algorithm was presented to me on usenet a > > few years ago. > > Your fallacy here seems to be in assuming that the way the > "meet-in-the-middle" algorithm decomposes the problem is the > *only* way to decompose the problem. It could be that *if* the > way it decomposes the problem were the only way to do it, then > that algorithm would be the fastest. However, other algorithms > for NP-complete problems use completely different approaches to > decomposition. I'm not sure I understand which part of my logic you don't agree with. I never said the meet-in-the-middle algorithm is the only way to treat or decompose the problem. > > > 2) The Collatz Conjecture is unprovable, if it is true. > > Here the problem seems to lie in the statement "any proof > of the Collatz conjecture must specify vector (x_0, x_1, ..., > x_B)". The statement that the "proof must specify" the vector > is vague and I don't think it can be made more precise. That's a fair criticism. I did say in the paper that it was an "informal" argument. A precise argument can be found in one of the papers in my bibliography that I wrote about the Collatz Conjecture. > > > 3) The Riemann Hypothesis is unprovable, if it is true. > > I didn't check this one because I can't remember what I > learned before about the RH. But there may be a similar problem. > > As a meta-note, I think the reason that your post was not > responded to for over 10 days may be that it seems very unlikely > that someone could solve 3 of the most famous unsolved problems > in math/CS in a relatively informal, 11-page paper with a lot of > introductory exposition. There have been examples of > "outsiders" solving important problems, the most famous possibly > being Paul Cohen, who proved the independence of the continuum > hypothesis. But IIRC, even Cohen was a trained mathematician; > it's just that his training was not in the sub-area of > mathematical logic. Your overall problem, IMHO, is that you > don't write about the mathematical concepts with the extremely > high degree of precision that is necessary to carry out > convincing proofs. To have a convincing proof, it is necessary for the reader to be convinced. My goal was not to give a convincing proof, because I have no control over the reader's thoughts. My goal was to provide a good enough explanation so that if the reader desires to be convinced, then he has the tools to do such. I hope I have done such. The paper was accepted for publication, and I am rewriting it. I will take your comments into consideration. Thanks, Craig > > --Jamie. (Celebrating (?) 20 years on Usenet!) > andrews .uwo } Merge these two lines to obtain my e-mail address. > @csd .ca } (Unsolicited "bulk" e-mail costs everyone.)
From: tchow on 24 Mar 2006 16:14 In article <1142214105.805669.311690(a)v46g2000cwv.googlegroups.com>, Craig Feinstein <cafeinst(a)msn.com> wrote: >2) The Collatz Conjecture is unprovable, if it is true. A very interesting argument. Using the same idea, we can prove: Theorem. If it is true that every positive integer has a finite binary representation, then this fact is unprovable. Proof. Consider the algorithm that prints n mod 2 and then iterates this process on floor(n/2). In order to be certain that this algorithm will halt, it is necessary to know whether n is even or odd at each step. Suppose that B is the number of bits in a hypothetical text-file containing a proof that every positive integer has a finite binary sequence. There is a mathematical theorem that there must exist a number n with the last B+1 bits of its binary representation equal to any given binary sequence. But this vector is random, so B+1 bits are required to specify it, contradicting the assumption that B is the number of bits in a text-file containing the alleged proof. Thus a formal proof cannot exist. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences
From: Craig Feinstein on 24 Mar 2006 16:21
t...(a)lsa.umich.edu wrote: > In article <1142214105.805669.311690(a)v46g2000cwv.googlegroups.com>, > Craig Feinstein <cafeinst(a)msn.com> wrote: > >2) The Collatz Conjecture is unprovable, if it is true. > > A very interesting argument. Using the same idea, we can prove: > > Theorem. If it is true that every positive integer has a finite binary > representation, then this fact is unprovable. > > Proof. Consider the algorithm that prints n mod 2 and then iterates > this process on floor(n/2). In order to be certain that this algorithm > will halt, it is necessary to know whether n is even or odd at each step. > Suppose that B is the number of bits in a hypothetical text-file containing > a proof that every positive integer has a finite binary sequence. There > is a mathematical theorem that there must exist a number n with the last > B+1 bits of its binary representation equal to any given binary sequence. > But this vector is random, so B+1 bits are required to specify it, > contradicting the assumption that B is the number of bits in a text-file > containing the alleged proof. Thus a formal proof cannot exist. > -- > Tim Chow tchow-at-alum-dot-mit-dot-edu > The range of our projectiles---even ... the artillery---however great, will > never exceed four of those miles of which as many thousand separate us from > the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences Tim, I thought you were more thoughtful than this. Read my response to the earlier post. |