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?
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))
.