Re: paper claiming p=np and soap bubbles
Dr Chaos
> tor...@diku.dk (Torben Ćgidius Mogensen) wrote in message news:<7z4qojy...@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.
I think it is an enormous assertion.
It is more correct to say that our human-derived models of classical
physics in the thermodynamic ordinary regime can compute things like
Turing machines. That is, you can compute things classically thinking
in terms of 'gears n levers' (babbage machine) if you look at
macroscopic physics and assume everything is big and cool enough that
thermodynamic fluctuations have "zero" chance for making
nondeterministic transitions.
that's a model, and an approximation of Nature.
> 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,
This is unknown. With a different computational model, things
which used to be in equivalent classes may no longer be.
> why shouldn't nature?
why should it? Nature does what it wants. (just like the journal ;) )
> 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.
see, that's why saying "nature ''is'' a Turing machine" is such a
difficult question and a highly unobvious assertion.
Loreno Heer
1. cs.CC/0406056 [abs, ps, pdf, other] :
Title: P=NP
Authors: Selmer Bringsjord, Joshua Taylor
Subj-class: Computational Complexity; Artificial Intelligence
There are also papers that say NP!=P :
4. cs.CC/0310060 [abs, ps, pdf, other] :
Title: Evidence that P is not equal to NP
Authors: Craig Alan Feinstein
Comments: 4 pages. Modified to improve writing style
Subj-class: Computational Complexity
ACM-class: F.1.3
so the false ones have to be sorted out first.
Russell Easterly
"Dr Chaos" <mbkennelS...@NOSPAMyahoo.com> wrote in message
> see, that's why saying "nature ''is'' a Turing machine" is such a
> difficult question and a highly unobvious assertion.
>
But, it is easy to compute if we assume time is "quantized".
Let's say our TM has a clock speed of Planck's time, 10^-43 sec.
There are 3.2 * 10^7 seconds in a year.
The observable universe is about 3 * 10^10 lightyears in diameter.
So, our TM can perform ~10^61 operations in 30 billion years.
Let every boson in the unverse be used as a TM.
Assume there are 10^80 bosons in the universe.
We could perform 10^141 computations
if we utilize every boson from the beginning of time
until the death of the universe.
Of course, the number of processors becomes astronomical
if we allow every photon to be used as a TM.
Even so, the number of computational steps we could perform
would be a "small" finite number.
Russell
- 2 many 2 count
(ps - one photon could perform 10^34 operations in a nanosecond)
Dr Chaos
>
> "Dr Chaos" <mbkennelS...@NOSPAMyahoo.com> wrote in message
>
>> see, that's why saying "nature ''is'' a Turing machine" is such a
>> difficult question and a highly unobvious assertion.
>>
>
> But, it is easy to compute if we assume time is "quantized".
> Let's say our TM has a clock speed of Planck's time, 10^-43 sec.
> There are 3.2 * 10^7 seconds in a year.
> The observable universe is about 3 * 10^10 lightyears in diameter.
> So, our TM can perform ~10^61 operations in 30 billion years.
OK, but quantization in physical quantum mechanics is not the same
thing as a naive discretization.
It's actually pretty subtle in the quantum optics regime---in the
specific mathematical terms it comes down to assuming some commutation
relations are small but finite instead of being zero as they would be
for classical fields. It's not really easy to explain intuitively at all.
Nevertheless, the dynamics of quantum mechanics is generally a whole lot
more continuous than fully discrete-time-discrete-state classical things like
turing machines which have a perfectly well defined state at all times and
a global "increment time" operator, neither of which is really the case
for QM, especially relativistically.
In fact I think some effort on 'quantum computing' really works
because the 'wave function' evolves in a more continuous space than
conventional (thermodynamically dissipative) computers! The more
continuous computational model there may not be equivalent to Turing
machines. I'm not an expert here though.
> Let every boson in the unverse be used as a TM.
> Assume there are 10^80 bosons in the universe.
> We could perform 10^141 computations
> if we utilize every boson from the beginning of time
> until the death of the universe.
>
> Of course, the number of processors becomes astronomical
> if we allow every photon to be used as a TM.
> Even so, the number of computational steps we could perform
> would be a "small" finite number.
that's saying that we've made some kind of simplified model
of Nature which is like a turing machine (in a vague and unproven way).
But it's not clear by any means that nature really is like that.
> Russell
> - 2 many 2 count
>
> (ps - one photon could perform 10^34 operations in a nanosecond)
now that's silly.
Now if you were in a classical continuous dynamics regime, say with chaotic
systems, then there would be a more clear discrete analog. What
you do there is to first take a Poincare section through the state space
and project a continuous flow to iteration on the map---you now have
discrete time (though the original time intervals are not necessarily
uniform) and continuous space.
At that point, if you can then create a "generating partition", then
the dynamics on this continuous space might be mappable one-to-one to
shift operators on a discrete symbol stream.
Now chaos is not as computationally complex as a Turing machine
(memory) but it seems that it would be more possible to define
classical mechanical system which might be equivalent starting from
this basis.
Reinier Post
>Have experiments been done to show that it is only a local minimum
>that is reached by soap bubbles and not a global minimum or is this
>just the party line?
You can make some wire frames and see for yourself. It's not too hard
to create something that's obviously bistable and can be "flipped"
from one local optimum to another by blowing. It's not hard to bend
such a case to make one of the optima obviously better than the other.
E.g. start with a cube.
--
Reinier
Scott Aaronson
> that is reached by soap bubbles and not a global minimum or is this
> be smarter than we give it credit.
>
> I'd be willing to make a gentleman's bet that no one can site a paper
> which describes an experiment that shows that the global minimum is
> not always acheived with soap bubbles.
Motivated by this newsgroup discussion, this week I did the
experiment. At a hardware store I bought two 8"x9" glass plates;
paint to mark grid points on the plates; thin copper rods which I cut
into 1" pieces; suction cups to attach the rods to the plates; Murphy
liquid oil soap; and a plastic tub to hold the soapy water. I also
bought work gloves, since at one point I cut my hand handling the
glass.
I found instances of the Euclidean Steiner Tree problem at the
OR-Library website:
http://mscmga.ms.ic.ac.uk/jeb/orlib/esteininfo.html
I concentrated on instances with 3-5 vertices. My favorite was one
with 5 vertices at the following locations: (.7, .96), (.88, .46),
(.88, .16), (.19, .26), (.19, .06). The optimal tree for this
instance has Steiner points at (0.2436870996, 0.1903058256) and
(0.7994693507, 0.2645412617) connecting the four lower vertices; and a
long edge connecting (.7, .96) to (.88, .46).
I didn't do any statistical analysis. What follows are informal
observations.
(1) Even though this experiment is standard folklore in CS, it *is*
cool to see it for yourself.
(2) By no means is the optimal tree always found. For example, with
the 5-vertex instance mentioned above, I sometimes got two edges
incident to (.7, .96), or else a Steiner point near the top.
Soap-bubble partisans might write that off as experimental error,
caused (for example) by slight inaccuracies in placing the pegs, or
the interference of my hands. But I also sometimes found triangular
"bubbles" of three Steiner vertices -- which is much harder to
explain, since such a structure could never occur in a Steiner tree.
(3) As alluded to above, the soap bubbles are very nondeterministic --
you might get a different tree each time you dunk. Occasionally I got
a tree that didn't even connect all the pegs.
(4) Another unexpected phenomenon was that sometimes the bubbles would
start in a suboptimal configuration, then slowly "relax" toward the
optimal one. Even with 4 or 5 pegs, this could take around 10
seconds; it's natural to conjecture that with more pegs it could take
longer. On the other hand, I don't predict that the optimal tree
would always be found, even given unlimited time for relaxation
(unless maybe one took quantum tunneling into account :) ).
In summary, I found no reason to doubt the "party line" -- that soap
bubbles do not solve NP-complete problems by magic. By analogy, a
rock in a mountain crevice could reach a lower-energy configuration by
rolling up first and then down, yet we don't observe it to do so.
Yesterday I gave a talk at Perimeter Institute on "NP-complete
Problems and Physical Reality," during which I demonstrated this
experiment for the audience. The slides are at
http://www.cs.berkeley.edu/~aaronson/npcomplete.ppt
I'll post photos of the experiment once I have them.
--Scott Aaronson
Craig Feinstein
That's a shame. I guess I lost the gentleman's bet then. Nature was
designed to be smart, but there is no magic in it. But it is an
interesting question how it "chooses" the configuration. Why is it so
non-deterministic?
BTW, soap bubbles have some really interesting and difficult
mathematics involved. I remember attending a very entertaining and
educational lecture in 1992 by Frank Morgan who works at Williams
College, who is an expert on this subject.
Craig
Scott Aaronson
> Problems and Physical Reality," during which I demonstrated this
> experiment for the audience. The slides are at
> http://www.cs.berkeley.edu/~aaronson/npcomplete.ppt
> I'll post photos of the experiment once I have them.
Photo at
http://www.cs.berkeley.edu/~aaronson/soapbubble.jpg
Unfortunately, it looks like the edges leading to the top vertex had
'popped' by the time this photo was taken. But you can at least see
what the apparatus looks like.
--Scott
Craig Feinstein
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.
What I would like to know from any physicists out there is why do soap
bubbles work in such a way that they are able to solve the Steiner
tree graph problem?How is nature able to quickly solve problems that
we cannot solve quickly?
Craig
ste...@nomail.com
: The paper is the best argument I have heard for p=np, even though I
: Craig
How many processors does nature have?
Stephen
MorituriMax
> What I would like to know from any physicists out there is why do soap
> bubbles work in such a way that they are able to solve the Steiner
> tree graph problem?How is nature able to quickly solve problems that
> we cannot solve quickly?
Time... Lots and lots of time.
Example: Mosquitoes. How can Nature quickly create such a tiny advanced organic
machine?
Tongue in cheek... grin
xx
Craig Feinstein wrote:
> 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.
>
You mean can be modeled by a Turing machine in polynomial time? That
would be surprising.
Jim Nastos
> 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.
Soap bubbles tend not to work very well for larger instances (but this
is because of the fact that the instrucments used can not be arbitrarily
thin, which would be required to solve arbitrarily large instances.)
> What I would like to know from any physicists out there is why do soap
> bubbles work in such a way that they are able to solve the Steiner
> tree graph problem?How is nature able to quickly solve problems that
> we cannot solve quickly?
When you drop water on the ground, it eventually spreads itself out as
thin as possible... systems will always "try" to settle into some kind of
"ground state" (of least energy.) It is analogous to the least-action
principle and the path that light takes, say, through different mediums
with varying indices of refraction, or when light reflects off of
surfaces.
In the case of soap bubbles, nature just seems to apply a really fast
approximation which is accurate for small cases but breaks down at larger
instances (due to actual physical properties... i.e. it is physically
impossible to build arbitrarily thin rods to dip into soapy water.)
Many other NP-problems can be modeled as physical systems in which a
lowest-energy-state would correspond to a solution to the combinatorial
problem. You can find that "DNA computing" solves the clique problem, for
instance.
J
Jim Nastos
> 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.
Also, using physics to model problems does not really rely on the
combinatorial problem to be NP-Complete... why not take a problem that is
exp-time (and so NOT in P) and then have physics instantly provide a
solution... doesn't that seem a little contradictory?
J
news...@comcast.net
> 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.
I'm not sure what "physics on a macroscopic level can be modeled as a
Turing machine" means... Since arbitrary computations can be done on
a macroscopic level with the classic "Billiard Ball Computer",
including non polynomial time computations, the obvious interpretation
of that statement is demonstrably false.
--
That's News To Me!
news...@comcast.net
Piotr Wyderski
Craig Feinstein wrote:
> Basically, the argument is that since soap bubbles can be made to
> solve NP-complete problems
Hehe, when you have ~10^26 processors, every problem seems to be simple. :-)
> How is nature able to quickly solve problems that we cannot solve quickly?
"Following all paths", i.e. using quantum phenomena. :-)
BTW, is it known by now where the BQP class exactly is in PH?
Best regards
Piotr Wyderski
Robert Israel
Craig Feinstein <cafe...@msn.com> wrote:
>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.
>What I would like to know from any physicists out there is why do soap
>bubbles work in such a way that they are able to solve the Steiner
>tree graph problem?
They don't. Soap films find a local minimum. They don't always find
a global minimum. Other algorithms can also find local minima quickly.
This does not help much with NP-complete problems.
Robert Israel isr...@math.ubc.ca
Department of Mathematics http://www.math.ubc.ca/~israel
University of British Columbia
Vancouver, BC, Canada V6T 1Z2
Poker Joker
news:b671fc3e.0407...@posting.google.com...
The "solution" is only a very good approximation.
Bellview Hospital
"If you believe, as many do, that hypercomputational processes are always
merely mathematical, and never physically real, you can't be rational and at
the same time refuse to accept our case for P=NP."
What does that mean? Believe then I'm not rational, and refuse to accept
case? OR Not believe, and be rational and accept case?
** Clarity avoids you.
"Craig Feinstein" <cafe...@msn.com> wrote in message
news:b671fc3e.0407...@posting.google.com...
Torben Ægidius Mogensen
> 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
Craig Feinstein
Then how does it choose which local minimum to land on?
Craig
Lee Rudolph
>isr...@math.ubc.ca (Robert Israel) wrote in message news:<cchs8k$1vg$1...@nntp.itservices.ubc.ca>...
>> In article <b671fc3e.0407...@posting.google.com>,
>> Craig Feinstein <cafe...@msn.com> wrote:
...
>> >What I would like to know from any physicists out there is why do soap
>> >bubbles work in such a way that they are able to solve the Steiner
>> >tree graph problem?
>>
>> They don't. Soap films find a local minimum. They don't always find
>> a global minimum. Other algorithms can also find local minima quickly.
>> This does not help much with NP-complete problems.
>>
>> Robert Israel isr...@math.ubc.ca
>> Department of Mathematics http://www.math.ubc.ca/~israel
>> University of British Columbia
>> Vancouver, BC, Canada V6T 1Z2
>
>Then how does it choose which local minimum to land on?
Leaving the question of "choice" unaddressed, I will guess that the
system simply evolves along the gradient of the appropriate potential
function until it reaches a local (not necessarily global) minimum.
Perhaps (we're talking nature here, right?) things are further
sophisticated by (natural, not simulated) "annealing" (again, of
an appropriate sort), say, thermal noise that is very likely to
rather quickly kick the configuration of soap bubbles out of a
sufficiently shallow local-not-global minimum and set it off
down the flowlines of the gradient again. That still wouldn't
necessarily guarantee reaching a global minimum in every case.
Lee Rudolph
Julian Streicher
> 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.
The arguement sidesteps the point of the problem. I can have
infinitely
many pentiums solve an NP complete problem. That doesn't mean that
P=NP.
--
Posted via Mailgate.ORG Server - http://www.Mailgate.ORG
Christoph M. Wintersteiger
As some have already pointed out, the soap bubbles only approximate
the solution, and even if it was the global minimum that they converge
to, the lines drawn by the bubble are not straight (water tension) and
they fluctuate (Brownian motion). And still there's another problem:
The authors forgot to write down the solution, which is an integral
part of problem solving. I wouldn't want to (exactly!) measure a soap
bubble drawn outline that's not just not straight, it even changes
while I measure it and even worse, my measuring changes it too
(uncertainty principle)!
Nature may be quick, but it's quite unexact. And I'm thankful for it;
I wouldn't want all brothers, sisters and places to look the exactly
same.
just my two cent.
CM Wintersteiger
Btw, are there any response papers yet?
Craig Feinstein
> >> They don't. Soap films find a local minimum. They don't always find
> >> a global minimum. Other algorithms can also find local minima quickly.
> >> This does not help much with NP-complete problems.
> >>
> >> Robert Israel isr...@math.ubc.ca
>
> Leaving the question of "choice" unaddressed, I will guess that the
> system simply evolves along the gradient of the appropriate potential
> function until it reaches a local (not necessarily global) minimum.
> Perhaps (we're talking nature here, right?) things are further
> sophisticated by (natural, not simulated) "annealing" (again, of
> an appropriate sort), say, thermal noise that is very likely to
> rather quickly kick the configuration of soap bubbles out of a
> sufficiently shallow local-not-global minimum and set it off
> down the flowlines of the gradient again. That still wouldn't
> necessarily guarantee reaching a global minimum in every case.
>
> Lee Rudolph
Have experiments been done to show that it is only a local minimum
that is reached by soap bubbles and not a global minimum or is this
just the party line? I'd like to believe that nature was designed to
be smarter than we give it credit.
I'd be willing to make a gentleman's bet that no one can site a paper
which describes an experiment that shows that the global minimum is
not always acheived with soap bubbles.
Craig
Patrick Powers
Initial conditions.
Dr Chaos
>
> Have experiments been done to show that it is only a local minimum
> that is reached by soap bubbles and not a global minimum or is this
> just the party line? I'd like to believe that nature was designed to
> be smarter than we give it credit.
Why should Nature care about YOUR global minimum?
The existence of metastable states and glasses in statistical mechanics
belies the idea of any magic, and the many intermediate states in protein
folding.
What's funny is that spin glasses are used by theoreticians as
frustrated thermodynamic states where finding global energy minima is
hard (and there are many approximate algorithms), I think in some
cases representable as yes, logical satisfiability problems.
> Craig
ge...@bialer.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?