2 ms·
While there is widespread belief that physical processes can solve NP-complete problems, there isn't actually any evidence. Physical processes can get stuck in
by jerf 17y ago
While there is widespread belief that physical processes can solve NP-complete problems, there isn't actually any evidence. Physical processes can get stuck in local optima, which is another way of saying that they fail to solve the NP-complete problem you hand them.
Here's an account of someone who actually tried one in real life (it takes a couple of pages): http://www.scottaaronson.com/papers/npcomplete.pdf http://www.scottaaronson.com/papers/npcomplete.pdf
Personally I see no reason to believe this isn't true of all physical processes that "solve" an NP-complete problem.