0
$\begingroup$

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.

Improve this question
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Discrete lizard♦ Dec 18 '17 at 16:18
  • $\begingroup$ Construct a P-complete problem solvable in linear time (you can use padding to improve the running time), and use the time hierarchy theorem. $\endgroup$ – Yuval Filmus Dec 18 '17 at 16:23
  • $\begingroup$ 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$ $\endgroup$ – Anil Dec 19 '17 at 15:18
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 19 '17 at 15:38

Your Answer

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

Browse other questions tagged or ask your own question.