Search code examples
algorithmcomplexity-theory

Why is linear time reducible important


When proving the lower bound of a new problem by reducing an existing problem of known complexity to it the emphasis is on linear time reduction. I kind of guess that for greater than linear time (say omega n^2 which is greater than linear omega n) we can not compare the two problems. But how to say it formally.

Also, say the known problem is omega n^3. Will now a omega n^2 reduction safely prove that the unknown problem has n^3 complexity?


Solution

  • Here is a formal statement.

    Suppose that problem type A can be solved in time O(f(n).

    Suppose that problem B can be reduced in time O(g(n)) to a problem of size h(n).

    Then we can solve problem B in time O(g(n) + f(h(n))).

    Ideally we want the reduction to be fast and for the problem to not blow up too much. You generally can't do better than a linear time reduction since it takes linear time just to enter the problem. That is why that is the ideal.

    Note that if f(n) has a polynomial upper bound then "a problem of size h(n)" can be relaxed to, "a problem of size O(h(n))." This is often true, and saves a lot of effort. However an example where that kind of simplification fails is with f(n) = 2^n and h(n) = n+log(n)).