
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 NPcomplete 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

