Except for the undecidable unaries I have no idea if there is anything in the gap between $P/poly$ and $P$
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Very similar: cstheory.stackexchange.com/questions/1982/…. $\endgroup$– Yuval FilmusCommented May 7, 2015 at 22:43
-
$\begingroup$ more general, whether one can recognize a language in a complexity class with advice versus (not with) that same complexity class. $\endgroup$– vznCommented May 8, 2015 at 17:05
-
$\begingroup$ ^and the answer is? $\endgroup$– user6818Commented May 8, 2015 at 17:20
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
9
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.
answered May 7, 2015 at 22:42
-
$\begingroup$ 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? $\endgroup$– user6818Commented May 8, 2015 at 0:16
-
$\begingroup$ Right, all we really need is that $L$ not be decidable in exponential time. $\endgroup$ Commented May 8, 2015 at 0:22
-
$\begingroup$ 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? $\endgroup$– user6818Commented May 8, 2015 at 0:36
-
$\begingroup$ 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. $\endgroup$ Commented May 8, 2015 at 0:39
-
$\begingroup$ But the question is to find a decidable language in $P/poly$ which is not in $P$ ... $\endgroup$– user6818Commented May 8, 2015 at 0:45