Given that A reduces to B in $O(n^2)$ and B is solvable in $O(n^3)$, solve A

Suppose a problem A reduce to problem B and reduction is done in $$O(n^2)$$ time.

If problem B is solved in $$O(n^3)$$ time then what about the time complexity of problem A?

Approach:

A is reduced to B . Here reduction is done at polynomial time. Here B is solved in polynomial time. So A should also be in polynomial time.

Now A can not be harder than B, So I think A can be $$O(n^3)$$ or $$O(n^2)$$. But logically if I reduced A to B and if B is $$O(n^3)$$ then it makes no sense for A to be $$O(n^2)$$, else why would I reduce it to higher complexity? So A is $$O(n^3)$$.

But my doubt is, we say while reduction that A can not be harder than B then how can we decide whether it is $$O(n^2)$$ or $$O(n^3)$$. Or is this argument only valid for P, NP classes of problem when I say A can not be harder than B or B must be at least as hard as A?

Answer given is "A is $$O(n^3)$$", but why can't it be $$O(n^2)$$ as "A can not be harder than B" but can be of equal complexity? Or is reducibility just an argument for complexity classes?

Explain if possible how reduction actually works, and why I couldn't apply it to my problem.

You have a reduction, but you don't know what size the new problem will be.

Say you have an instance of problem A of size n. And you can reduce it to an instance of problem B in time O (n^2). If you can reduce it to an instance of size $$O(N^{1/2})$$ then you are fine: You took O (N^2) for the reduction, and $$O(N^{3/2})$$ to solve the instance of B.

If you reduce the instance of problem A to an instance of size O (n log n) of problem B, then you will take O (n^3 log^3 n) to solve the instance of B.

So the time for the reduction and the time for solving B are not enough. You need to know the size of the new problem as well. (Of course you can't create an instance greater than O (n^2) in O (n^2) time, so the worst case is O (n^6), but it could be much better).

The answer that was given (O (n^3)) is definitely wrong. It doesn't follow from the information you were given.

• can you answer my doubt in the comments below – CHETAN RAJPUT Dec 4 '18 at 10:33

Given an $$O(n^2)$$ reduction from $$A$$ to $$B$$ and an $$O(n^3)$$ algorithm for solving $$B$$, you can solve $$A$$ as follows:

• Given an instance of $$A$$ of size $$n$$, reduce it to an equivalence instance $$B$$ of size $$N = O(n^2)$$.
• Apply the algorithm for $$B$$, which runs in time $$O(N^3) = O(n^6)$$.

If we know more about the size of the $$B$$-instance produced by the $$O(n^2)$$ reduction, we might be able to tighten this analysis.

Also, all of this only gives an upper bound on the complexity of $$A$$. There might be other ways of solving $$A$$. Stated differently, the complexity of $$A$$ could be much smaller than $$O(n^6)$$.

• If an algorithm used to covert the problem takes O(n^2) and reduced problem solved in O(n^3) then wont it be max(n^2,n^3 ) ? How n^2*n^3 as an upper bound for A ? – CHETAN RAJPUT Dec 4 '18 at 1:52
• I am not exactly getting what you said, can you add some more points ? – CHETAN RAJPUT Dec 4 '18 at 1:54
• For some reason you're assuming that the reduction maintains the size of the instance. This need not be the case. A reduction running in time $O(n^2)$ can produce an instance of that size. – Yuval Filmus Dec 4 '18 at 1:57
• Then why answer given is O(n^3) i mean How they are so sure , it could be O(n^2) too i think ? – CHETAN RAJPUT Dec 4 '18 at 2:02
• The output size cannot be exponential. Any transformation that runs in O (n^2) can only produce output of size O (n^2) at most. To produce output of size O (n^4), for example, would take at least O (n^4) time. – gnasher729 Dec 4 '18 at 9:39