NP-complete Problems and Physical Reality
arXiv:quant-ph/0502072
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.
23 pages, minor corrections
References in corpus (12)
- A Quantum Adiabatic Evolution Algorithm Applied to Random Instances of an NP-Complete Problem
- The holographic principle
- Strengths and Weaknesses of Quantum Computing
- Simulation of topological field theories by quantum computers
- Nonlinear quantum mechanics implies polynomial-time solution for NP-complete and #P problems
- Quantum lower bounds for the collision and the element distinctness problems
- Quantum Adiabatic Evolution Algorithms versus Simulated Annealing
- Subquantum Information and Computation
- Quantum Computing and Hidden Variables I: Mapping Unitary to Stochastic Matrices
- An efficient algorithm for the Riemannian 10j symbols
- Limits on Efficient Computation in the Physical World
- Quantum Computing and Hidden Variables II: The Complexity of Sampling Histories
Cited by in corpus (47)
- Jerusalem Lectures on Black Holes and Quantum Information
- Efficient quantum algorithm for dissipative nonlinear differential equations
- Stochastic thermodynamics of computation
- Quantum gravity computers: On the theory of computation with indefinite causal structure
- Quantum computation with indefinite causal structures
- Operational quantum theory without predefined time
- Networks of non-equilibrium condensates for global optimization
- Quantitative approaches to information recovery from black holes
- Solving the subset-sum problem with a light-based device
- Optimal state discrimination and unstructured search in nonlinear quantum mechanics
- Quantum state cloning using Deutschian closed timelike curves
- Estimating distinguishability measures on quantum computers
- Dynamical structure factors of dynamical quantum simulators
- Fast optimization algorithms and the cosmological constant
- Limits on Efficient Computation in the Physical World
- Grover search and the no-signaling principle
- A model-theoretic interpretation of environmentally-induced superselection
- Can Intelligence Explode?
- Closed Timelike Curves Make Quantum and Classical Computing Equivalent
- Hybrid quantum computing with ancillas
- Construction of an NP Problem with an Exponential Lower Bound
- Solving NP-complete problems with delayed signals: an overview of current research directions
- Implementation of classical communication in a quantum world
- Nonlinear and non-CP gates for Bloch vector amplification
- Computability Theory of Closed Timelike Curves
- Can biological quantum networks solve NP-hard problems?
- Complexity Science for Simpletons
- Normalizer Circuits and Quantum Computation
- Entanglement, intractability and no-signaling
- Computational Complexity and the Nature of Quantum Mechanics
- Adding Methodological Testing to Naur's Anti-formalism
- Computability and Complexity of Unconventional Computing Devices
- Revisiting Integer Factorization using Closed Timelike Curves
- Postulate-based proof of the P != NP hypothesis
- Computational Complexity and the Nature of Quantum Mechanics (Extended version)
- No-signaling, intractability and entanglement
- Quantum information and statistical mechanics: an introduction to frontier
- Why is a soap bubble like a railway?
- Overview of Information Theory, Computer Science Theory, and Stochastic Thermodynamics for Thermodynamics of Computation
- A note on observables for counting trails and paths in graphs
- Ranks of gauge groups and an NP-complete problem on the Landscape
- Molecular recognition of the environment and mechanisms of the origin of species in quantum-like modeling of evolution
- Unobservable causal loops as a way to explain both the quantum computational speedup and quantum nonlocality
- A review of "Mem-computing NP-complete problems in polynomial time using polynomial resources" (arXiv:1411.4798)
- Computational costs of data definition at the quantum - classical interface
- Quantum randomness and free will
- One-in-Two-Matching Problem is NP-complete