# Showing TIME(n) is not closed under poly-time reduction

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..

• 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)$. Nov 18 at 21:47
• 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! Nov 18 at 23:59