6
$\begingroup$

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

Improve this question
$\endgroup$
8
  • $\begingroup$ What kind of optimality are you asking for? In particular, another algorithm with same or worste worst-case but better average case performance might well be considered better (Quicksort vs Bubblesort/Mergesort). You are talking O-Terms, right? I think what you are after is a lower runtime bound for the solved problem. $\endgroup$
    – Raphael
    Oct 8, 2010 at 20:22
  • $\begingroup$ I've tried to clarify above. I am interested in worst-case complexity (upper bound), and in O-terms as you suggest. You're right, also, in suggesting that I'm interested in whether or not there is a lower runtime bound for the solved problem. $\endgroup$
    – user1338
    Oct 8, 2010 at 20:38
  • 1
    $\begingroup$ Is “use reductions” an answer? See a related question. $\endgroup$
    – Tsuyoshi Ito
    Oct 8, 2010 at 21:26
  • $\begingroup$ This is a near duplicate of this question: cstheory.stackexchange.com/questions/1284/… - I vote to close unless the OP can clarify what's different $\endgroup$
    – Suresh Venkat
    Oct 8, 2010 at 21:46
  • $\begingroup$ Isn't this question too broad? $\endgroup$
    – arnab
    Oct 8, 2010 at 21:46

2 Answers 2

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
2
$\begingroup$

The biggest set of techniques I know for (unconditional) lower bounds is information theoretic ones. Unfortunately these techniques can't give better than linear-time lower bounds. (The lower-bound of $\Omega(n \log n)$ for comparison-based sorting is not actually super-linear since the effective input is the $\binom{n}{2}$ comparison results.) As Moritz says we're essentially clueless about how to prove superlinear unconditional lower bounds for natural problems and unrestricted computational models.

On the other hand if an algorithm is limited to sublinear space then there are techniques for showing superlinear lower bounds on time. If I recall correctly there are known more or less matching lower and upper bounds for e.g. sorting and median-finding when time is superlinear and space is sublinear. I think the product of space and time for sorting is always $\tilde \Omega(n^2)$ for a wide range of space and time between polylogarithmic and quadratic.

Improve this answer
$\endgroup$