scientific article; zbMATH DE number 1406123

MaRDI QIDQ4939149zbMATH OpenFDO

Authors Daniel S. Abrams, Seth Lloyd

Publication date 23 February 2000

zbMATH Keywords

computational complexityNP-complete problemspolynomial-time solutionlaws of physics

Mathematics Subject Classification ID

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

Recommendations

• Physical portrayal of computational complexity
• Physical consequences of \(P \neq\) NP and the density matrix renormalization group annealing conjecture
• P/NP , and the quantum field computer
• Quantum limit on computational time and speed
• scientific article; zbMATH DE number 1555956

Cited in

(15)

• Physical consequences of \(P \neq\) NP and the density matrix renormalization group annealing conjecture
• Quantum cellular automata, black hole thermodynamics and the laws of quantum complexity
• Physical portrayal of computational complexity
• Algorithmic arguments in physics of computation
• Quantum limit on computational time and speed
• Computability of physical operations
• Computational complexity of the landscape. I.
• 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
• Computational tractability -- beyond Turing?
• Discrete Lawvere theories and computational effects
• scientific article; zbMATH DE number 3958735 (Why is no real title available?)
• Increasing complexity with quantum physics
• Computational complexity of determining which statements about causality hold in different space-time models
• scientific article; zbMATH DE number 2187721 (Why is no real title available?)
• Uncomputability and physical law

This page was built for publication:

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