12 ms·
If you are interested in the implications of P vs. NP, as opposed to a survey of the situation around the problem, check out this excellent essay [1] by Scott A
by bmh100 10y ago
If you are interested in the implications of P vs. NP, as opposed to a survey of the situation around the problem, check out this excellent essay [1] by Scott Aaronson. He goes into interesting consequences about the nature of quantum computing, simulation of a human mind, and time travel, among other topics.
There is also another interesting article [2] by Arkady Bolotin at Ben-Gurion University in Israel, who argues that the lack of macroscopic quantum behavior implies P!=NP. Basically, macroscopic quantum behavior would imply that the universe is computing the solution to a NP-hard problem in violation with currently accepted laws of physics. Also, see this debate between Bolotin and an educated commenter [3].
[1]: http://www.scottaaronson.com/papers/philos.pdf http://www.scottaaronson.com/papers/philos.pdf [pdf]
[2]: https://medium.com/the-physics-arxiv-blog/the-astounding-link-between-the-p-np-problem-and-the-quantum-nature-of-universe-7ef5eea6fd7a#.hybznxnd5 https://medium.com/the-physics-arxiv-blog/the-astounding-lin...
[3]: https://www.researchgate.net/post/P_NP_and_quantum_nature_of_universe-any_thoughts https://www.researchgate.net/post/P_NP_and_quantum_nature_of...
- ikeboy 10y ago>The problem is that the equation says nothing about how large an object needs to be before it obeys Newtonian mechanics rather than the quantum variety. I'm pretty sure this is BS. The linked medium post does nothing to defend the implicit premise that the universe can be computed in a reasonable amount of time by classical computers.
- frozenport 10y agoIndeed it is, interference phenomena have so far scaled up to fairly large many atom structures in rather predictable ways. The real problem for Quantum mechanics starts happening when needing to explain gravity.
- dlubarov 10y agoI think you're talking past the parent, whose point is that our universe's physics may not be polynomial time computable (or computable at all, for that matter).
- ikeboy 10y agoI made two different points. The first is that there's nothing that "obeys Newtonian mechanics rather than the quantum variety.", it's quantum all the way up. The second is what you said. Guess it wasn't clear enough that the two points aren't related.
- nullc 10y agoI came here to recommend your [1] as well as http://www.cs.ucsd.edu/users/russell/average.ps http://www.cs.ucsd.edu/users/russell/average.ps
- robertelder 10y agoThe Wikipedia page has a section that does a pretty good job I think: https://en.wikipedia.org/wiki/P_versus_NP_problem#Consequences_of_solution https://en.wikipedia.org/wiki/P_versus_NP_problem#Consequenc... "Similarly, Stephen Cook says: ...it would transform mathematics by allowing a computer to find a formal proof of any theorem which has a proof of a reasonable length, since formal proofs can easily be recognized in polynomial time. Example problems may well include all of the CMI prize problems."
- harryjo 10y agoHow does "polynomial" imply "practically tractable"? If P = NP, the exponent may well something like x^100 or x^(# of atoms in the Universe)
- stonogo 10y agoBecause 'polynomial time' is a long-standing term in time complexity theory defined to imply tractability.
- bhrgunatha 10y agoYes, this always confuses me. Why the constants are swept under teh carpet for real world, practical applications. From the same article. "It is also possible that a proof would not lead directly to efficient methods, perhaps if the proof is non-constructive, or the size of the bounding polynomial is too big to be efficient in practice." Given the long standing nature of the problem, my guess is that some new techniques or insights will be required to solve it one way or the other. Those may well give clues to solving NP/NP-Complete problems efficiently. Until someone actually does it though it's still just speculation.
- Smaug123 10y agoAaronson specifically addresses this in section 1.2.1, on page 6.
- 10y ago
- rspeer 10y agoWait, doesn't that claim by Arkady Bolotin state the converse: that P != NP implies the lack of macroscopic quantum behavior?
- harryjo 10y agoYes. The post you are replying to said, essentially, "lack of macroscopic quantum behavior => P != NP, because macroscopic quantum behavior => P=NP", which is obviously flawed logic.
- coldtea 10y ago>Basically, macroscopic quantum behavior would imply that the universe is computing the solution to a NP-hard problem in violation with currently accepted laws of physics This seems to presuppose what it tries to prove.