Complexity Theory for Simpletons
in [Theory]
|
Prev: HEAP SORT
Next: Greedy Algorithm
From: Woeginger Gerhard on 31 Mar 2006 03:34 Craig Feinstein <cafeinst(a)msn.com> wrote: # Let me say it another way. In my paper, my model of computation is a # person named Mabel who works as a computer in the 1930's. I'm assuming # that Mabel lives forever, never gets tired of working, and never slows # down with age. (I also deal with another computer named Mildred also # working back then in the 1930's.) As you probably know, computers back # then were people. Nobody had the fancy definitions for models of # computation back then that we have today. Sometimes these fancy # definitions can really lead a person to see only trees but not see the # forest. # # Suppose that Mabel were given the Meyer auf der Heide algorithm to # solve subset-sum. Do you really believe the propaganda that you have # been fed from the "Computer Science Establishment" (don't worry, I'm # only joking and not claiming that there is a real conspiracy except for # Microsoft) that Mabel is going to work in polynomial time with such an # algorithm? # # For input n=1000, do you really believe that it's going to take Mabel # only 1000^16 time to do such a calculation? The code of such a # nonuniform algorithm increases in size exponentially with n, so Mabel # would not even be able to stay in her "computer room" when n=1000. She # would have to have much more than trillions of pages of instructions to # implement such an algorithm and would have to travel around quite a bit # to read the code. Essentially, just because the computer scientists say # this algorithm runs in polynomial time, if you apply it in real life, # it's going to still be exponential time. I understand. Whenever you use terms like "algorithm", "computation", "running time", "P", and "NP in your paper, then these terms do not have the standard meaning used in computer science, but some different meaning that is based on your private notion of "Mabel" and "real life". And your paper has nothing to do with the P-versus-NP question that came up in computer science in the 1970s, but it deals with a different P-versus-NP question that is based on your private notion of "Mabel" and "real life". And in your private model with "Mabel" and "real life", you can prove that P is not equal to NP. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Woeginger Gerhard on 31 Mar 2006 03:42 Craig Feinstein <cafeinst(a)msn.com> wrote: # # Suppose that Mabel were given the Meyer auf der Heide algorithm to # solve subset-sum. # # For input n=1000, do you really believe that it's going to take Mabel # only 1000^16 time to do such a calculation? The code of such a # nonuniform algorithm increases in size exponentially with n, As far as I know, this is not known to be true. It's an open question. Yes, the code of the Meyer auf der Heide algorithm increases exponentially in size with n. But: There might be other non-uniform algorithms that solve SUBSET-SUM in polynomial time and whose code size grows only polynomially in n. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Woeginger Gerhard on 31 Mar 2006 03:57 Craig Feinstein <cafeinst(a)msn.com> wrote: # # The P vs. NP question is a question which applies to people like Mabel # and Mildred, not some crazily defined model of computation cooked up by # some computer scientist. That's why it's a good question and why I # worked on it. You should clearly state this in your paper!!! ================================ For your information: The Clay Mathematics Institute (CMI) will award a prize of $1.000.000 for a proof or a disproof of the P vs. NP question IN THE MODEL OF COMPUTATION COOKED UP BY THE COMPUTER SCIENTISTS: http://www.claymath.org/millennium/ I think that most of the discussion in this newsgroup is based on the terrible misunderstanding, that your paper tries to contribute to the solution of the ClayMath problem, whereas your paper discusses the P vs. NP question in the Mabel-Mildred-Feinstein model. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: sillybanter on 31 Mar 2006 09:58
Craig Feinstein <cafeinst(a)msn.com> wrote: > For input n=1000, do you really believe that it's going to take Mabel > only 1000^16 time to do such a calculation? The code of such a > nonuniform algorithm increases in size exponentially with n, so Mabel > would not even be able to stay in her "computer room" when n=1000. She > would have to have much more than trillions of pages of instructions to > implement such an algorithm and would have to travel around quite a bit > to read the code. Essentially, just because the computer scientists say > this algorithm runs in polynomial time, if you apply it in real life, > it's going to still be exponential time. So what, IN YOUR PROOF, specifically disallows non-uniform algorithms. "I don't like them" is not sufficient. "They're not realistic" isn't good enough either. Either your argument is mathematically sound, or it isn't, and in this case it isn't. > The P vs. NP question is a question which applies to people like Mabel > and Mildred, *You're* P vs. NP question may apply to Mabel and Mildred, but the one the rest of the world is interested in is the standard one. > not some crazily defined model of computation cooked up by > some computer scientist. Actually, the P vs. NP is *precisely* a problem in a "defined model of computation cooked up by some computer scientist." > That's why it's a good question and why I > worked on it. And unfortunately for you, no one else cares about your question. And to add insult to injury, even within your dreamed up model your proof isn't correct. -- Steve Stringer sillybanter(a)gmail.com |