News for hackers. Stuff that matters.
Re:Why Philosophers Should Care About Computational Complexi... by nabla9 on Thursday June 16, 2016 @09:28AM (#11915899)
>So, is there a physical effect that cares about computational complexity?

The No-SuperSearch Postulate (there is no physical means to solve NP-complete problems in polynomial time) is not purely mathematical conjecture. It's also a claim about the laws of physics. The postulate includes P != NP as a special case, but it is stronger.

If you assume that the postulate is true, you can use it to explain things like why quantum mechanics is linear, why adiabatic systems have small spectral gaps, why timeline curves don't exist, black hole information paradox, impossibility of relativity computers, why QM-amplitudes are not directly observable. The question of how much physics you could derive from No-super-search postulate is interesting.

Re:Why Philosophers Should Care About Computational Complexi... by stared on Thursday June 16, 2016 @10:10AM (#11916195)
And it is assumption I find... strange. If it really works, it would be interesting.

QM is linear for many other reasons (the simplest related to not being able communicate faster than light); smallness of spectral gaps is AFAIK a conjuncture.

And in general, playing with causality will bring many other problems.

Re:Why Philosophers Should Care About Computational Complexi... by Cybiote on Thursday June 16, 2016 @12:34PM (#11917205)
The principle is essentially a recognition that, if there were no constraints on energy or other physical limits, then many problems in NP or harder would be tractable. This bridge might be two-way, so we may start from complexity and ask: what bounds might we expect in physics since without, this problem would be tractable?

One relevant example is protein folding, which is NP-complete. Why then have we not found arrangements such that protein conformations are solutions to NP-complete problems? It's reasonable to postulate that nature does not actually solve NP-complete problems and that almost all carriers of problematic instances died off (not completely, since prions exist after all).

If this is the case then we can make a prediction that there exists some polynomial time algorithm able to predict conformations of biologically encountered instances in reasonable time to high accuracy and that a program search such as deep learning will one day find this algorithm given sufficient data. That would be a huge deal.

+++

The following links argue more or less that from a bayesian perspective, a prior weighted heavily on smaller exponents for the case P=NP, is more reasonable given the examples and rarity of realistically intractable polynomial time algorithms (and how quickly they seem to fall to reasonable with focused attention).

Paragraph 3 in http://www.scottaaronson.com/democritus/lec6.html

Argument 1 in https://windowsontheory.org/2013/05/06/reasons-to-care-in-ho...

Re:Why Philosophers Should Care About Computational Complexi... by btilly on Thursday June 16, 2016 @01:22PM (#11917514)
If this is the case then we can make a prediction that there exists some polynomial time algorithm able to predict conformations of biologically encountered instances in reasonable time to high accuracy and that a program search such as deep learning will one day find this algorithm given sufficient data. That would be a huge deal.

People have been pursuing this path for a long time. See, for example, http://www.ef.uns.ac.rs/mis/archive-pdf/2011%20-%20No4/MIS20... for an algorithm for the traveling salesman problem based on how ants work.

Re:Why Philosophers Should Care About Computational Complexi... by sgt101 on Thursday June 16, 2016 @05:19PM (#11918955)
Hang on - proteins folding "unpredictably" as per a prion is not evidence of solving of NP completeness in that "problem". Also, while prions might do that, it's not clear to me that there is much evidence that their folding is "unpredictable" in any rigorous way. Can you cite a reference?
Re:Why Philosophers Should Care About Computational Complexi... by Cybiote on Friday June 17, 2016 @01:05PM (#11923830)
Yea, I'm saying prions show that nature is not solving NP-complete problems. What we have instead is that a class of well behaved proteins were selected for but there can still be problematic instances.