Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR02-062 | 19th November 2002 00:00

Classical Physics and the Church-Turing Thesis

RSS-Feed




TR02-062
Authors: Andrew Chi-Chih Yao
Publication: 19th November 2002 09:50
Downloads: 1879
Keywords: 


Abstract:

Would physical laws permit the construction of computing machines
that are capable of solving some problems much faster than the
standard computational model? Recent evidence suggests that this
might be the case in the quantum world. But the question is of
great interest even in the realm of classical physics. In this
paper, we observe that there is fundamental tension between the
Extended Church-Turing Thesis and the existence of numerous
seemingly intractable computational problems arising from
classical physics. Efforts to resolve this incompatibility could
both advance our knowledge of the theory of computation, as well
as serve the needs of scientific computing.



ISSN 1433-8092 | Imprint