Re:Markets are efficient if and only if P=NP (2010)
by qsort on Wednesday October 21, 2020 @08:30AM
(#24847114)
NP-complete problems can be polynomially reduced to each other. If you had a magical oracle that was able to solve any one specific NP-complete problem in O(1) time, you could turn that into a O(n^k) solution for all NP-complete problems.
That's the idea behind DNA-computing, for instance.
The question is whether it is actually possible to do so at a reasonable cost and at scale.
Regardless, what "nature" does has 0 to do with P vs NP, computability or anything else. P vs NP is a statement strictly about mathematical objects, there is no notion of "nature" anywhere in it.
That's the idea behind DNA-computing, for instance.
The question is whether it is actually possible to do so at a reasonable cost and at scale.
Regardless, what "nature" does has 0 to do with P vs NP, computability or anything else. P vs NP is a statement strictly about mathematical objects, there is no notion of "nature" anywhere in it.