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

cs.stackexchange https://cs.stackexchange.com/questions/100982

  •  05-11-2019
  •  | 
  •  

سؤال

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.

لا يوجد حل صحيح

مرخصة بموجب: CC-BY-SA مع الإسناد
لا تنتمي إلى cs.stackexchange
scroll top