What techniques are used for proving algorithms optimal? Possible Duplicate:
  Problems that can be used to show polynomial time hardness results  




Given a polynomial time algorithm, what techniques are known for proving that an algorithm is optimal?  E.g., given an algorithm for solving, say, REACH (a P-complete problem), what are good techniques for proving that the algorithm runs with optimal complexity, assuming of course that it does and that its complexity is known.

In case that was unclear, I'll restate my question briefly:  Given a polynomial time algorithm that decides a language or computes a function, how can one prove that the algorithm's worst-case complexity cannot be improved upon with a "better" algorithm?

Edit:  By "better" what I mean is that, e.g., if a particular algorithm has been established to run in O(n^4), there does not exist any algorithm with O(n^3) complexity that solves the same problem.

Thank you,

Philip
Intuitively, proving that a problem in P requires, say, time $\Omega(n\log n)$ is not any easier than proving the same lower bound for SAT. In fact, proving this lower bound for SAT should be easier, because we think SAT is harder than any problem in P. Concrete examples are matrix multiplication or fourier transform over GF(2). These are polynomial time problems but we don't have superlinear lower bounds.

One notable exception are time hierarchy results which give you (artificial) problems that are solvable by a Turing machine in time $O(t(n))$ but not solvable in time $O(t(n)/\log(n)).$ These results are proved via diagonalization.