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

  • $\begingroup$ $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$. $\endgroup$
    – Steven
    Nov 11, 2023 at 19:16
  • $\begingroup$ 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$? $\endgroup$
    – Meki21
    Nov 11, 2023 at 19:20
  • $\begingroup$ 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$. $\endgroup$
    – Steven
    Nov 11, 2023 at 19:30
  • $\begingroup$ Ohh I see it now - I didn’t recognise contradiction through this structure $\endgroup$
    – Meki21
    Nov 11, 2023 at 20:00
  • $\begingroup$ What exactly is your question? Please ask only one question per post. Please make sure to articulate your question explicitly. A question normally ends in '?'. $\endgroup$
    – D.W.
    Dec 8, 2023 at 20:56


Your Answer

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

Browse other questions tagged or ask your own question.