DocumentCode
1278504
Title
Computational complexity for physicists
Author
Mertens, Stephan
Author_Institution
Otto-von-Guericke Univ., Magdeburg, Germany
Volume
4
Issue
3
fYear
2002
Firstpage
31
Lastpage
47
Abstract
The theory of computational complexity has some interesting links to physics, in particular to quantum computing and statistical mechanics. The article contains an informal introduction to this theory and its links to physics
Keywords
computational complexity; physics; quantum computing; quantum theory; statistical mechanics; Eulerian circuits; Hamiltonian cycles; Ising models; coloring; combinatorial problems; complexity classes; computational complexity; decision problems; intractable problems; nondeterministic algorithms; phase transitions; physics; polynomial reductions; probabilistic analysis; quantum computing; quantum parallelism; satisfiability; statistical mechanics; time complexity; tractable problems; tractable trees; Computational complexity; Computer science; Mathematics; Particle measurements; Physics computing; Quantum computing; Sorting; Time measurement; Turing machines; Upper bound;
fLanguage
English
Journal_Title
Computing in Science & Engineering
Publisher
ieee
ISSN
1521-9615
Type
jour
DOI
10.1109/5992.998639
Filename
998639
Link To Document