# Showing for decidable language that is in $P/poly$ but not in $P$ (follow-up)

I've been trying to wrap my head around the proof provided in this answer. I understand that $$P$$ is a class where languages can be decided by a Turing Machine and that $$P/poly$$ is a bigger class that also includes languages that can be decided by circuits.

Take a language $$L$$ which is not in $$\mathsf{E} = \bigcup_{c=1}^\infty \mathsf{TIME}(2^{cn})$$. Now consider the language $$L' = \{1^m : m \in L\}$$. Then $$L'$$ is clearly in $$\mathsf{P/poly}$$, but it's not in $$\mathsf{P}$$: if it were decidable in time $$O(m^k)$$, then we could decide $$L$$ in time $$O((2^n)^k)$$, and so $$L$$ would be in $$\mathsf{E}$$. Our decision procedure works as follows: on input $$m$$ of length $$n = \log m$$, we run the algorithm for $$L'$$ on the input $$1^m$$. This runs in time $$O(m^k) = O((2^n)^k)$$.

It remains to ensure that $$L'$$ is decidable. To that end, all we need to do is to choose some $$L \notin \mathsf{E}$$ which is decidable, for that makes $$L'$$ trivially decidable: given an input, if it's not of the form $$1^m$$, reject; otherwise, answer according to whether $$m \in L$$.

The existence of a decidable language $$L \notin \mathsf{E}$$ is guaranteed by the time hierarchy theorem.

I have a couple of questions about the understanding of this proof.

Then I am confused as to how we first define language $$L$$ to not be in $$E$$ and then we show that actually is in $$E$$ since $$L^{'}$$ can be computed within the limits...

• $P$ and $E$ are not the same. By the time-hierarchy theorem $P \subseteq \text{TIME}(2^{n}) \subsetneq \text{TIME}(2^{2n}) \subseteq E$. Nov 11, 2023 at 19:16
• Oh thank you! But still, $L$ is firstly said to not be in $E$ but then we show that is runs in $O((2^{n})^{k})$ and hence is in $E$? Nov 11, 2023 at 19:20
• Are you familiar with proofs by contradiction? The answer is choosing $L \not\in E$ and then showing that $L' \not\in P$ by contradiction. To do so it assumes that $L' \in P$ and concludes that this would imply $L \in E$. Since this is indeed a contradiction (as $L \not \in E$), it must be $L' \not\in P$. Nov 11, 2023 at 19:30
• Ohh I see it now - I didn’t recognise contradiction through this structure Nov 11, 2023 at 20:00