[Solved]: What is the decidable language in $P/poly$ but not in $P$?

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

Asked By : user6818

Answered By : Yuval Filmus

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.
Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42283