Re: paper claiming p=np and soap bubbles

From: Torben Ęgidius Mogensen (torbenm_at_diku.dk)
Date: 07/08/04 

Date: 08 Jul 2004 09:45:08 +0200

cafeinst@msn.com (Craig Feinstein) writes:

> The paper is the best argument I have heard for p=np, even though I
> believe the opposite. It can be found here:
> http://arxiv.org/abs/cs.CC/0406056
> It brings out a great question.
>
> Basically, the argument is that since soap bubbles can be made to
> solve NP-complete problems, particularly the Steiner tree graph
> problem, in what appears to be polynomial time and physics on a
> macroscopic level can be modeled as a Turing machine, it must be true
> that p=np.

P vs. NP is a matter of how fast you can solve problems on Turing
machines. P are problems that take polynomial time on a deterministic
Turing machine, while NP are problems that can be solved on a
nondeterministic Turing machine (essentially a Turing machine with
unbounded but finitely branching parallelism). The P=NP problem is
about whther the NP problems can be solved in polynomial time on a
deterministic Turing machine.

The article you cite has three assumptions:

 1) A Turing machine can emulate nature.

 2) Nature can solve NP problems fast.

 3) A deterministic Turing machine can emulate nature in polynomial
    time.

The first assumption can be argued, but it by no means an established
fact.

The second assumption is established only for simple cases of NP
problems - once they get too complicated, "natural" methods invented
so far (including the soap bubble Steiner solution) finds only
approximations, not optimal solutions. I would say this question is
still open.

The third assumption is very debatable. When you get to the quantum
level, nature works more like a nondeterministic machine than a
deterministic machine, so I very much doubt nature can be emulated in
polynomial time on a determinsitic machine (unless P=NP, which make
sthe argument circular).

        Torben

Relevant Pages

  • Re: paper claiming p=np and soap bubbles
    ... > macroscopic level can be modeled as a Turing machine, ... P are problems that take polynomial time on a deterministic ... A Turing machine can emulate nature. ... A deterministic Turing machine can emulate nature in polynomial ...
    (sci.physics)
  • Re: paper claiming p=np and soap bubbles
    ... > macroscopic level can be modeled as a Turing machine, ... P are problems that take polynomial time on a deterministic ... A Turing machine can emulate nature. ... A deterministic Turing machine can emulate nature in polynomial ...
    (comp.theory)
  • Please Help
    ... Instead of a deterministic Turing machine, ... The theoretical notion of "quick" used here is that of an algorithm ... in polynomial time, so this problem is in '''NP'''. ...
    (sci.math)
  • Re: paper claiming p=np and soap bubbles
    ... P are problems that take polynomial time on a deterministic ... >> nondeterministic Turing machine (essentially a Turing machine with ... >> 1) A Turing machine can emulate nature. ... physics in the thermodynamic ordinary regime can compute things like ...
    (comp.theory)
  • Re: paper claiming p=np and soap bubbles
    ... P are problems that take polynomial time on a deterministic ... >> nondeterministic Turing machine (essentially a Turing machine with ... >> 1) A Turing machine can emulate nature. ... physics in the thermodynamic ordinary regime can compute things like ...
    (sci.math)