firstname.lastname@example.org (Torben ÃÂÃÂgidius Mogensen) wrote in message news:<email@example.com>...
> 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?