Timeline for Could an NP-hard problem have a mechanical or physical solution method?
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 19, 2020 at 19:34 | comment | added | The T | How so that unless P=NP? What if someone creates an entirely new machine. That's non-classical and proves they are not equal to classical machines? Now, we have a new machine that's proven to solve np-complete problems in polynomial time, but is revolutionary and so much different than classical machines. | |
| Jun 8, 2015 at 10:08 | comment | added | Raphael | For all we know, the process of an apple falling down a tree is impossible to simulate. All we have is a model (gravitation laws, general relativty, ...) with finite precision, which we can only approximate up to finite precision. That's three uncertainties already. | |
| Jun 8, 2015 at 9:30 | comment | added | Tom van der Zanden | @Raphael The second part of my answer partially addresses this. In order to identify a $NP$-hard problem that can be solved efficiently using a mechanical process, we would need to identify some physical process we can't simulate efficiently with sufficient accuracy. Given that computational problems are discrete (i.e. languages) a discrete approximation of the physical process should often suffice. Even if there existed such a process that could not be simulated, it would certainly be non-obvious (since nobody has managed to name one so far) so the answer to the question is "no" regardless. | |
| Jun 8, 2015 at 7:05 | vote | accept | user34391 | ||
| Jun 8, 2015 at 7:05 | |||||
| Jun 8, 2015 at 7:02 | comment | added | Raphael | "we could run a physics simulation on a computer to get the same result" -- how so? For all we know, we can not accurately simulate real physics (as opposed to some clunky model of it) on computers. | |
| Jun 7, 2015 at 19:18 | history | answered | Tom van der Zanden | CC BY-SA 3.0 |