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

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 ]
gersh@bialer.com

Posts: 12
Registered: 12/13/04
Re: paper claiming p=np and soap bubbles
Posted: Jul 9, 2004 1:58 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply


torbenm@diku.dk (Torben Ægidius Mogensen) wrote in message news:<7z4qojymbf.fsf@pc-032.diku.dk>...

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


I don't think it is too much of a stretch to say nature can be modeled
by a turing machine in polynomial time. Otherwise, maybe Turing
machines should be redefined. I think the more complicated problem is
how you define. However, if quantum computers can theoretically
compute NP problems in P time, why shouldn't nature?

Although, if we determine a physical process coresponds to a Turing
machine, we still need to define what we mean by the physical system's
time. Physically time may not be equivalent steps, but rather to
entropy. In other words, does the interaction of every molecule with
every molecule corespond to a step in a turing machine, or does the
interaction of a bunch of water with a bunch of metal count as one
unit of time. The definition you choose the turing program that is
being modeled. Even if they produce the same result, one could take NP
time, and other P time.

Another possibility for dealing with time, could involve considering
entropy. According to the laws of physics, it may be possible to show
a turing machine requires creating a certain amount of entropy. This
could then be put into corespondance with a physical system.

The concept of discovering mathematical truths from physical processes
is an interesting concept. Could the proof of say, some number theory
theorem, which required checking all the results up to some large
number be verifiable by astronomical observations. Some large-scale
universal phenomena would have to correspond to the problem, and parts
of the effect of a small pertubation related to the problem would have
to be really big. Would it be mathematics if the truth was
probabilistic due to quantum effects. You could truly have this
theorem is true with probability 99.5283%. Would this be equivalent to
a limit theorem?



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.