On 02 Oct 2014, at 20:19, meekerdb wrote:
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.
This is very plausible.
The problem in measuring the complexity of the folding problem is that
we need to formalize it at some level, in functional term to
distinguish the polynomially verifiable and the non polynomially search.
I think today the folding of protein is still not simulable. Complex
proteins don't even fold correctly in the laboratory, and some don't
fold correctly in the cytoplasme if some other genes does not
function. Indeed some complex protein needs special build cavities,
where the folding is guided by the helps of other proteins. Prion
disease are supposed to be "contagious folding problem" between some
protein (usually found in the brain).
I agree it is not quite plausible, with respect to the available
evidence, that folding exploits quantum coherence. But *many*
molecules might exploits enough of quantum coherence to get quantum
fault tolerant, and I am not entirely convinced that this is
impossible for the cytoplasm, either.
Bruno
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
http://iridia.ulb.ac.be/~marchal/
--
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 [email protected].
To post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
