|
|
Re: paper claiming p=np and soap bubbles
Posted:
Jul 9, 2004 1:58 PM
|
|
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?
|
|
