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.
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...