0
$\begingroup$

I am trying to wrap my head around the following proof

  • Choose some language A $\in$ $TIME(n^3)$ \ $TIME(n)$ (the existence of such a language is guaranteer by the hierarchy theorem)
  • Let B = {1}
  • Note that $A \leqslant_{p} B, B \in TIME(n)$ but $A \not\in TIME(n^{3})$

The way I understand is that A is in $TIME(n^{3})$ but not in $TIME(n)$. I assume the main point in the proof is the polynomial reduction to B, but can we say that it is more or less than $n^{3}$?

I guess I would understand that in case the reduction can be completed in $O(n)$ then A can actually be solved in $TIME(n)$ which indeed is a contradiction..

Improve this question
$\endgroup$
2
  • $\begingroup$ A cannot be solved in time $O(n)$ by hypothesis. The proof is not a proof contradiction, it is exhibiting two languages $A, B$ such that $B \in TIME(n)$ but $A \not \in TIME(n)$, yet $A \le_p B$, which means that $TIME(n)$ is not closed under poly-time reductions. The time spent to compute the reduction does not matter (as long as it is polynomial, which can be guaranteed to be the case since $A$ can be solved in polynomial time by hypothesis). Also, you have a typo in the last item, it should be $A \not\in TIME(n)$. $\endgroup$
    – Steven
    Nov 18 at 21:47
  • $\begingroup$ Ahh I see. But why does it not matter what is the time of the reduction? Oh yes the typo now makes sense, thank you! $\endgroup$
    – Meki21
    Nov 18 at 23:59

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.