# What is the decidable language in $P/poly$ but not in $P$?

Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$

• Very similar: cstheory.stackexchange.com/questions/1982/…. – Yuval Filmus May 7 '15 at 22:43
• more general, whether one can recognize a language in a complexity class with advice versus (not with) that same complexity class. – vzn May 8 '15 at 17:05
• ^and the answer is? – user6818 May 8 '15 at 17:20

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.
• Not clear :) Why this curious choice of $2^{2^{\vert x\vert}}$? I don't understand the motivation. And is this language that you are contructing even outside NP? – user6818 May 8 '15 at 0:16
• Right, all we really need is that $L$ not be decidable in exponential time. – Yuval Filmus May 8 '15 at 0:22
• How do do you know that your language $L'$ is decidable as is required to be shown? But all that one wanted was to show a language outside $P$. But you are showing something even outside $EXP$ (which is a superset of $NP$). Why did one have to go this strong? Are you even outside NEXP? – user6818 May 8 '15 at 0:36
• On the contrary, $L'$ is not decidable. But it is in (for example) $\mathsf{NC^0}/1$, see if you can find out why. As for why I chose $L$ to be outside of $\mathsf{E}$, it's because that's how my proof works. The proof only works if $L$ is outside of $\mathsf{E}$. Other proofs could differ. – Yuval Filmus May 8 '15 at 0:39
• But the question is to find a decidable language in $P/poly$ which is not in $P$ ... – user6818 May 8 '15 at 0:45