Complexity Theory for Simpletons
in [Theory]
|
Prev: HEAP SORT
Next: Greedy Algorithm
From: Woeginger Gerhard on 28 Mar 2006 06:47 Craig Feinstein <cafeinst(a)msn.com> wrote: # #> Which computer (or computer model) did you have in mind? # # Certainly not a laptop for reasons that you pointed out. Just a # theoretical computer that can take arbitrarily large input. The # specifics of the model of computation are not necessary for the # argument in the paper to work. But this just cannot be true! We know several models of computation, in which P=NP holds. If the specifics of the model of computation are not necessary for your argument to work, then your argument must also work in all the models of computation with P=NP. Since your argument claims P not equal NP in all models of computation, your argument must be horribly wrong. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Woeginger Gerhard on 28 Mar 2006 07:03 Craig Feinstein <cafeinst(a)msn.com> wrote: # I'm afraid you misunderstood the definition of "better". With respect # to the definition of "better" used in my paper, no algorithm has been # found that beats Meet-in-the-Middle. But you do not provide any definition of "better" in your paper. If you would tell us what you mean by "better", then we might be able to help you and to guide you to the central mistake in your argument. --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Woeginger Gerhard on 28 Mar 2006 07:42 Craig Feinstein <cafeinst(a)msn.com> wrote: # I'm afraid you misunderstood the definition of "better". With respect # to the definition of "better" used in my paper, no algorithm has been # found that beats Meet-in-the-Middle. If you think I'm lying, then just # read Woeginger's 2003 article cited in my paper No, no, no, no, no. Woeginger's 2003 article has NOTHING to do with the discussion in this thread. =========================== All algorithms in this 2003 article are uniform algorithms in the RAM-model. The model of computation in Feinstein's paper is unspecified. =========================== In the 2003 article, the running time of an algorithm A is its **ASYMPTOTIC** worst case running time. Feinstein considers the number of steps for **ONE** particular value of n. =========================== --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/
From: Craig Feinstein on 28 Mar 2006 11:16 You make a good point, Gerhard. In my paper, I am excluding non-uniform algorithms from consideration for obvious reasons. Craig
From: Woeginger Gerhard on 29 Mar 2006 02:40
Craig Feinstein <cafeinst(a)msn.com> wrote: # You make a good point, Gerhard. In my paper, I am excluding non-uniform # algorithms from consideration for obvious reasons. No, you do not exclude them. 1. In fact, your entire argument discusses non-uniform algorithms. You stated explicitly to us, that you are only interested in the number of steps with respect to ONE particular value of n. 2. What the heck do you mean by "I am excluding non-uniform algorithms". In your line of argument, there is not a single spot where the issue of uniform/non-uniform would show up. Hence, the whole argument applies to all types of algorithms, might they be uniform or non-uniform, or whatever. Since your argument leads to a wrong conclusion in the case of non-uniform algorithms, your argument clearly is **FAULTY**. 3. What do you mean by excluding non-uniform algorithms from consideration "for obvious reasons"??? --Gerhard ___________________________________________________________ Gerhard J. Woeginger http://www.win.tue.nl/~gwoegi/ |