News for hackers. Stuff that matters.
Re:Markets are efficient if and only if P=NP (2010) by MaxBarraclough on Wednesday October 21, 2020 @08:24AM (#24847061)
Doesn't that line of argument only work if nature's algorithms can be shown to be both precise (giving exact solutions) and complete (able to solve every valid problem)?
Re:Markets are efficient if and only if P=NP (2010) by est31 on Wednesday October 21, 2020 @11:58AM (#24849064)
Yeah I doubt that nature is able to solve problems above a certain size. After you put together a certain number of soap bubbles they'll collapse into a black hole. Furthermore there are concerns of speed of light or speed of sound.

Nature might give efficient solvers for specific problems up to a certain size, but we already have "practical" NP problem solvers in classical silicon in the form of SMT solvers.

Re:Markets are efficient if and only if P=NP (2010) by MaxBarraclough on Wednesday October 21, 2020 @04:17PM (#24851630)
> we already have "practical" NP problem solvers in classical silicon in the form of SMT solvers.

They're out there, and practical for some problems, but SMT solvers aren't exactly a solved problem. They're used for deductive proofs about program correctness, which are still pretty finicky. [0]

[0] https://blog.adacore.com/using-spark-to-prove-255-bit-intege...

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.