3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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 ? $\endgroup$ – CHETAN RAJPUT Dec 4 '18 at 1:52
  • $\begingroup$ I am not exactly getting what you said, can you add some more points ? $\endgroup$ – CHETAN RAJPUT Dec 4 '18 at 1:54
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 4 '18 at 1:57
  • $\begingroup$ Then why answer given is O(n^3) i mean How they are so sure , it could be O(n^2) too i think ? $\endgroup$ – CHETAN RAJPUT Dec 4 '18 at 2:02
  • 1
    $\begingroup$ 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. $\endgroup$ – gnasher729 Dec 4 '18 at 9:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.