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.