[benten10]

For those who may not be aware -- As always in these situations: Scott Aronson said it first!

For reference, here's the highly amusing and interesting paper he's written on this:

"NP-complete Problems and Physical Reality" http://www.scottaaronson.com/papers/npcomplete.pdf

Abstract:

"Can NP-complete problems be solved efficiently in the physical universe? I survey proposals including soap bubbles, protein folding, quantum computing, quantum advice, quantum adiabatic algorithms, quantum-mechanical nonlinearities, hidden variables, relativistic time dilation, analog computing, Malament-Hogarth spacetimes, quantum gravity, closed timelike curves, and “anthropic computing.” The section on soap bubbles even includes some “experimental” results. While I do not believe that any of the proposals will let us solve NP-complete problems efficiently, I argue that by studying them, we can learn something not only about computation but also about physics."

[dogecoinbase]

A favorite example of mine, using photons to solve Traveling Salesman in quadratic time: https://www.osapublishing.org/oe/abstract.cfm?id=140598

Spoiler: the number of photons required scales up so quickly that the phenomenon cannot be observed for sufficiently high N.