Computational complexity theory is the study of the amount of time, memory, gates, and other machine resources needed to solve computational problems. Current knowledge of computing requirements is far less precise than the ancient Greeks' knowledge of astrophysics. One of the seven "Millennium Prize Problems" carrying a $1M bounty from Harvard's Clay Mathematics Institute (www.claymath.org) is the "P versus NP Question". This boils down to whether there is (or is not) a vastly better algorithm for determining whether a given Boolean formula in n variables is a tautology, than the grade-school method of trying all 2^n rows of its truth table, which uses 2^n gates and hence 2^n time. Thousands of other computational problems are known to be equivalent to this one.
Much of the uncertainty owes to the current lack of good
connections between computational complexity and long-studied
mathematical notions of complexity. Thirty years ago a connection was
proved between the number of gates needed to compute a function
f(x_1,...,x_n) and the