This of course is, arguably, the seminal problem -- does P=NP? If one accepts counterfactual definetiveness in QM (and CT as true, of course), then the problem takes on a whole new dimension from the persepctive of Bell's Theorem -- perhaps, even more interestingly, different conclusions suggest themselves depending on whether inhomogeneous (IBI) and homogeneous (HBI) Bell inequalities are considered. The epistemic, metaphysical, and foundational repurcussions of such an analysis may well prove especially profound. In this regard, how would an affirmative or negative answer to P = NP reflect on the schism between classical physics and QM that Bell's Theorem seems to suggest?
.
I fear that this may be an apples vs. oranges question. P vs. NP has to do with determinism, while the results regarding Bell's Inequalities are intrinsically stochastic. QBP, or Quantum Bounded Polynomial time is a non-deterministic complexity class because the very theoretical foundations of Quantum Mechanics, which include the Heisenberg uncertainty principle, are by nature non-deterministic and stochastic. This is not to say there can't be some OTHER foundation to physics that is comparable to QM that itself is deterministic. In my opinion, an answer that P=NP will point to the existence of such a kind of deterministic physics. However, because we don't have thin kind of physics quite yet, does not imply that P!=NP. If P!=NP, it probably does imply that there is no such deterministic physics.
While generally familiar with Bell's theorem, I'm not so familiar with the subtle differences between IBI and HBI, so I will leave that issue to be resolved by another writer.
None. P=NP (or not) is a question of classical computer science. It doesn't have anything to do with quantum mechanics. Bell's theorem is a mathematical statement about quantum mechanics, so its assumptions are completely independent of the assumptions underlying classical computer science, also. That quantum algorithms can evade the constraints of classical computer science was shown, constructively, by the algorithms of Shor and Grover and the work that these spawned; and (some) constraints on what quantum algorithms can do ``better'' than classical algorithms were established by Farhi, Goldstone and collaborators.
- Badges
- Science topic
- Similar topics
- Physical Sciences
- Quantum Physics