Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math.independent

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   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
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


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



Date Subject Author
7/7/04
Read paper claiming p=np and soap bubbles
Craig Feinstein
7/7/04
Read Re: paper claiming p=np and soap bubbles
stephen@nomail.com
7/7/04
Read Re: paper claiming p=np and soap bubbles
MorituriMax
7/7/04
Read Re: paper claiming p=np and soap bubbles
xx
7/7/04
Read Re: paper claiming p=np and soap bubbles
Jim
7/7/04
Read Re: paper claiming p=np and soap bubbles
Jim
7/7/04
Read Re: paper claiming p=np and soap bubbles
newstome@comcast.net
7/7/04
Read Re: paper claiming p=np and soap bubbles
Phil Freedenberg
7/7/04
Read Re: paper claiming p=np and soap bubbles
Thomas Nordhaus
7/7/04
Read Re: paper claiming p=np and soap bubbles
Piotr Wyderski
7/7/04
Read Re: paper claiming p=np and soap bubbles
Robert Israel
7/8/04
Read Re: paper claiming p=np and soap bubbles
Craig Feinstein
7/8/04
Read Re: paper claiming p=np and soap bubbles
Lee Rudolph
7/8/04
Read Re: paper claiming p=np and soap bubbles
Craig Feinstein
7/9/04
Read Re: paper claiming p=np and soap bubbles
Dr Chaos
7/27/04
Read Re: paper claiming p=np and soap bubbles
Reinier Post
7/29/04
Read Re: paper claiming p=np and soap bubbles
Scott Aaronson
7/30/04
Read Re: paper claiming p=np and soap bubbles
Craig Feinstein
8/3/04
Read Re: paper claiming p=np and soap bubbles
Scott Aaronson
7/9/04
Read Re: paper claiming p=np and soap bubbles
Patrick Powers
7/7/04
Read Re: paper claiming p=np and soap bubbles
Poker Joker
7/7/04
Read Re: paper claiming p=np and soap bubbles
Bellview Hospital
7/8/04
Read Re: paper claiming p=np and soap bubbles
Arthur J. O'Dwyer
7/11/04
Read Re: paper claiming p=np and soap bubbles
Loreno Heer
7/8/04
Read Re: paper claiming p=np and soap bubbles
Torben Mogensen
7/9/04
Read Re: paper claiming p=np and soap bubbles
gersh@bialer.com
7/9/04
Read Re: paper claiming p=np and soap bubbles
Dr Chaos
7/9/04
Read Re: paper claiming p=np and soap bubbles
Jesse F. Hughes
7/8/04
Read Re: paper claiming p=np and soap bubbles
Julian Streicher
7/8/04
Read Re: paper claiming p=np and soap bubbles
Christoph M. Wintersteiger
7/8/04
Read Re: paper claiming p=np and soap bubbles
Thomas Nordhaus

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.