Re: Another claim for P=NP

From: Eray Ozkural exa (examachine_at_gmail.com)
Date: 10/27/04

  • Next message: Mitch Harris: "Re: Problem creating a regular expression." 
    Date: 27 Oct 2004 12:49:13 -0700

    "John P. Green" <foo@bar.com> wrote in message news:<fAHdd.729135$Gx4.299781@bgtnsc04-news.ops.worldnet.att.net>...
    > "Alex Hunsley" <lard@tardis.ed.ac.molar.uk> wrote in message
    > news:10ncfc8csi6mif1@corp.supernews.com...
    > > Eray Ozkural exa wrote:
    > > > I'm not sympathetic for claims that P=NP, but here is another one by
    > > > Bringsjord and Taylor that a friend referred me to.
    > > >
    > > > http://kryten.mm.rpi.edu/scb.pnp.solved14.pdf
    > >
    >
    > Ho hum. Basically they claim that a simple soap film device can solve the
    > Steiner tree problem, which is NP-complete, and you can similate the soap
    > film
    > device digitally. Now despite what might appear in some naive physics text
    > book,
    > I'm pretty damn sure that on a large Steiner tree problem the soap film
    > device will
    > find a local minimum, not a global minimum. My dog can find local minima.

    It's pretty silly, I know. I heard the "soap film device" claim
    somewhere else and I didn't like it at all. I still don't know who had
    the original "idea". An EE friend of mine sent the paper to me, and he
    said that somebody said the paper was good or something like that, in
    favor of the paper, so I wanted to ask you guys if you knew about this
    particular paper. I had told him in advance that some person, who is
    too self-confident, claims to have solved the problem every 3-4
    months. (Which is something perhaps that does not happen in the
    electrical engineering community :)

    This may be come to seen as a snakeoil-salesman position, like that of
    "dna computing" which would have us fill the oceans with genetic
    material to solve *small* instances of TSP. And this is even worse,
    because it doesn't even do an exhaustive search of any kind... In my
    opinion, it's too clear that a soap film device cannot execute a
    complete search... regardless of the problem it's trying to solve.

    Next we will have quantum physicists showing an absurd quantum
    phenomena which uses vacuum energy to solve an NP-complete problem in
    a space-time region with 0 volume.

    Just throw the problem into a black hole, and it will take care of
    itself :) Even faster than soap bubbles.

    Cheers, 

    --
Eray Ozkural
  • Next message: Mitch Harris: "Re: Problem creating a regular expression."