= 27d567bc2d48d9f40e9ccc20ea370b15)
Eliezer_Yudkowsky comments on Thoughts on the Singularity Institute (SI) - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
= 783df68a0f980790206b9ea87794c5b6)
Loading…= b715d02e85f7b3b4ae65ca3d3e450868)
Subscribe to RSS Feed
Powered by Reddit
= f037147d6e6c911a85753b9abdedda8d)
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (1270)
Kawoomba, there is no known case of any NP-hard or NP-complete solution which physics finds.
In the case of proteins, if finding the lowest energy minimum of an arbitrary protein is NP-hard, then what this means in practice is that some proteins will fold up into non-lowest-energy configurations. There is no known case of a quantum process which finds an NP-hard solution to anything, including an energy minimum; on our present understanding of complexity theory and quantum mechanics 'quantum solvable' is still looking like a smaller class than 'NP solvable'. Read Scott Aaronson for more.
One example here is the Steiner tree problem, which is NP-complete and can sort of be solved using soap films. Bringsjord and Taylor claimed this implies that P = NP. Scott Aaronson did some experimentation and found that soap films 1) can get stuck at local minima and 2) might take a long time to settle into a good configuration.
Heh. I remember that one, and thinking, "No... no, you can't possibly do that using a soap bubble, that's not even quantum and you can't do that in classical, how would the soap molecules know where to move?"
Well. I mean, it's quantum. But the ground state is a lump of iron, or maybe a black hole, not a low-energy soap film, so I don't think waiting for quantum annealing will help.
waves soap-covered wire so it settles into low-energy minimum
dies as it turns into iron
I also seem to recall Penrose hypothesizing something about quasicrystals, though he does have an axe to grind so I'm quite sceptical.
I saw someone do the experiment once (school science project). Soap bubbles are pretty good at solving three- and four-element cases, as long as you make sure that all the points are actually connected.
I don't think that three- and four-element cases have local minima, do they? That avoids (1) and a bit of gentle shaking can help speed up (2).
Yup.