principleMinor
Given that A reduces to B in $O(n^2)$ and B is solvable in $O(n^3)$, solve A
Viewed 0 times
reducessolvablethatsolveandgiven
Problem
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.
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.
Solution
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.
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.
Context
StackExchange Computer Science Q#100982, answer score: 3
Revisions (0)
No revisions yet.