The distinction between polynomial-time and exponential-time algorithms should be a part of everybody's general knowledge. Briefly, some examples of polynomial-time algorithms are the gravitational N-body problem and matrix inversion. The classical N-body problem involves N*N interactions. If you double the number of bodies, there is four times as much number-crunching to do. This is said to be an O(N*N) problem. The need for matrix inversion arises in many problems. An NxN matrix needs N*N*N operations to invert it, so this is an O(N*N*N) algorithm. Well, there are plenty of programs around to run these algorithms, so polynomial-time algorithms are do-able on computers. Many clever refinements of algorithms are concerned with converting an O(N*N) algorithm to O(NlogN).
The concept of exponential-time algorithms arose from the travelling salesman problem, where one has to find the shortest route around a network, visiting each node just once if possible. It turns out that while there exist polynomial-time algorithms which are pretty good at guessing an answer, the only way to know for sure is the examine every route. The computational workload is proportional to
N
s
where s is some number and N is the number of nodes.
Another example of exponential-time behaviour is the standard quantum N-particle problem, treated as an initial-value problem. This runs in 3N dimensions of space, and if there are M computational nodes in each dimension, where M=100 say, then the workload is proportional to
3N
M
Consider what this means. Each extra particle we add will multiply the workload a million times. Care to run this as a simulation on your computer?
Exponential-time algorithms are practically useless for large N. Whenever possible, we want to find a polynomial-time algorithm to do the job, and if it cannot be found, we might as well give up.
James Baugh (1) has argued that a polynomial-time algorithm for the quantum N-particle problem doesn't exist. This is irrespective of the question of EPR-completeness. Baugh's argument is almost certainly true. The consequences are that through the idiom of computer simulation we may show our understanding of quantum mechanics for small systems, but big systems are apparently off limits.