NP-Complete Problems and Physical Reality (2005)
1–10 of 34 posts
Re: NP-Complete Problems and Physical Reality (2005)
#2If you enjoyed this I highly recommend both his book, "Quantum Computing Since Democritus", and blog (http://www.scottaaronson.com/blog/). Tagline of the blog is "If you take just one piece of information from this blog:
Quantum computers would not solve hard search problems
instantaneously by simply trying all the possible solutions at once."
Re: NP-Complete Problems and Physical Reality (2005)
#3I remember a TED talk on the failed attempts to find cases in which nature solves a NP-complete problem. Paper must be an interesting read.
Re: NP-Complete Problems and Physical Reality (2005)
#4"But another reason we believe P≠NP is that otherwise mathematical creativity could be automated!"
I have a problem with this. Just because the thought is unpleasant does not make it true or false. Besides, perhaps this is the very difference between automation and intelligence, perhaps the point at which you can ask this of a computer is the point at which you should no longer consider it a computer.
Re: NP-Complete Problems and Physical Reality (2005)
#5On the point of anthropic computing: it is important to note that you have not accomplished any _improvement_ to your condition by killing yourself; before as after, you had found a correct solution with probability 2^-n. Anthropic computing is just "fancy guessing".
What is interesting about it to me is that the "true computational nature of reality" must be such that sufficient computation is available for you to run the _validation_ of your solution in logarithmic time an exponential number of times ("in parallel"), because otherwise you could not find yourself _at all_ in a universe where you knew you had found the correct computation. Which does make it strange that quantum physics does not seem to give us any way to "get at" all this computation that must be going on behind the scenes.
(Unless the "true nature" of reality is such that a subset of the wavefunction is being computed "for cheap". Collapse exonerated?)
Re: NP-Complete Problems and Physical Reality (2005)
#6I posted this link because (a) it seemed like a good survey of the subject, and (b) I felt like I almost understood most of it. Does anyone have any suggestions for accessible further reading at the intersection of computer science and physics?
Re: NP-Complete Problems and Physical Reality (2005)
#7A point that has become more obvious over the years is this: there are "soft" instances of NP-complete problems where you can find good approximations in reasonable time, and there are "crunchy" instances of the same class of problem where you don't find a good approximation.
Commercial ILP solvers (e.g. Gurobi, CPlex) profit from the fact that quite often it is possible to formulate NP-complete problems and find good solutions in acceptable time. Similarly, many of the "physical" ways of solving NP-complete problems work ok for easy instances and get unwieldly fast if confronted with difficult instances.
Re: NP-Complete Problems and Physical Reality (2005)
#8I posted this link because (a) it seemed like a good survey of the subject, and (b) I felt like I almost understood most of it. Does anyone have any suggestions for accessible further reading at the intersection of computer science and physics?
His Philosophy-Complexity paper is also fantastic, in case you have not read it already: http://www.scottaaronson.com/papers/philos.pdf
It has also been discussed most recently here: https://news.ycombinator.com/item?id=9061744
Re: NP-Complete Problems and Physical Reality (2005)
#9"But another reason we believe P≠NP is that otherwise mathematical creativity could be automated!" I have a problem with this. Just because the thought is unpleasant does not make it true or false. Besides, perhaps this is the very difference between automation and intelligence, perhaps the point at which you can ask this of a computer is the point at which you should no longer consider it a computer.
Sure, it is certainly possible that mathematics can be automated, but mathematics is also over 2000 years old. We are not much closer to automating it than the Greeks were. P=NP does not only break the Complexity theory (which is a relatively new invention), it also has profound consequences to all of human reasoning.
Re: NP-Complete Problems and Physical Reality (2005)
#10"But another reason we believe P≠NP is that otherwise mathematical creativity could be automated!" I have a problem with this. Just because the thought is unpleasant does not make it true or false. Besides, perhaps this is the very difference between automation and intelligence, perhaps the point at which you can ask this of a computer is the point at which you should no longer consider it a computer.
Or you should no longer consider yourself something else than a computer.