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
What techniques are used for proving algorithms optimal?
cc.complexity theory;proofs