Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: paper claiming p=np and soap bubbles
Replies: 30   Last Post: Aug 3, 2004 1:07 AM

 Messages: [ Previous | Next ]
 Torben Mogensen Posts: 60 Registered: 12/6/04
Re: paper claiming p=np and soap bubbles
Posted: Jul 8, 2004 3:45 AM

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