On 10/2/2014 7:20 AM, Bruno Marchal wrote:
NP-hard problem are computable...
Yes.
they just take exponential time to solve.
Assuming that P ≠ NP, which is indeed judged very plausible by all experts
(but
not all) in the field, but remains still unproved today. It is as you know
a famous
open problem.
This is why I find protein folding intriguing. I see the following
possibilities:
-> Molecular interactions entail an immense computational power;
Assuming the very linear base of QM is correct, that is the case. A priori to emulate
exactly an hydrogen atom, you need a continuum of universal numbers, that is, assuming
that comp and the derivation are correct, we need a computer exploiting its FPI
statistics on the limit of all computations (in the FPI sense) to emulate even a very
little piece of "matter". I guess this means that we need a quantum computer.
Now, if our subst level is classical, it would mean that a rough classical emulation of
the behavior of the molecules would be enough, and that might be polynomially computable
in the length of the (arbitrary) input.
That might still require high parallelism in practice, and the polynomial idea of
simplicity is still quite theoretical, as in practice an high degree polynomial on a
high input remains intractable.
The folding of protein molecules in biological systems is catalyzed by the presence of
other molecules. Because of the decoherence produced by all the interactions in solution
it is essentially classical - which it would have to be in order to function reliably in
cell metabolism.
Brent
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to everything-list+unsubscr...@googlegroups.com.
To post to this group, send email to everything-list@googlegroups.com.
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.