Computational complexity of physical law

DOI10.1007/3-540-49208-9_14MaRDI QIDQ4939149zbMATH OpenFDO

Authors Daniel S. Abrams, Seth Lloyd

Publication date 23 February 2000

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-49208-9_14

zbMATH Keywords

computational complexitylaws of physicsNP-complete problemspolynomial-time solution

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Quantum computation (81P68)

Recommendations

• Physical portrayal of computational complexity
• Physical consequences of P NP and the density matrix renormalization group annealing conjecture
• P/NP , and the quantum field computer
• Quantum limit on computational time and speed
• Quantum computation and NP-complete problems

Cited in

(16)

• Computability of physical operations
• Quantum limit on computational time and speed
• Computational tractability -- beyond Turing?
• If many physicists are right and no physical theory is perfect, then by using physical observations, we can feasibly solve almost all instances of each NP-complete problem
• Physical consequences of P NP and the density matrix renormalization group annealing conjecture
• scientific article; zbMATH DE number 3958735 (Why is no real title available?)
• Physical portrayal of computational complexity
• P/NP , and the quantum field computer
• Algorithmic arguments in physics of computation
• Quantum cellular automata, black hole thermodynamics and the laws of quantum complexity
• Increasing complexity with quantum physics
• scientific article; zbMATH DE number 2187721 (Why is no real title available?)
• Uncomputability and physical law
• Discrete Lawvere theories and computational effects
• Computational complexity of the landscape. I.
• Computational complexity of determining which statements about causality hold in different space-time models

This page was built for publication: Computational complexity of physical law

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4939149)