# Linear time reduction equivalence

I have to show if the following statement is true or false. Suppose we have two problems $A$ and $B$. We want to know whether the following is true:

If $A \le_p B$ and there is an algorithm which solves $B$ in linear time, then there is an algorithm which solves $A$ in linear time as well.

So we recently started with polynomial time reductions and I am not sure what to do for this problem.

• A hint: is there any good reason why linearity of the algorithms is preserved under polynomial time reductions? If so, try to use that for a proof. If not, try some examples and see if you can find a counterexample. In case you're still stuck, perhaps this answer can shed light on another approach. – Discrete lizard Dec 18 '17 at 16:18
• Construct a P-complete problem solvable in linear time (you can use padding to improve the running time), and use the time hierarchy theorem. – Yuval Filmus Dec 18 '17 at 16:23
• I would use as a counter example the factorizing problem. Multiplyling two prime numbers will be in $P$ where factorizing a given integer to its prime factors is in $NP$ – Anil Dec 19 '17 at 15:18
• It is not known how to multiply two prime numbers in linear time, and it is not known that factorization is any harder than multiplication. – Yuval Filmus Dec 19 '17 at 15:38