5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very similar: cstheory.stackexchange.com/questions/1982/…. $\endgroup$ – Yuval Filmus May 7 '15 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$ – vzn May 8 '15 at 17:05
  • $\begingroup$ ^and the answer is? $\endgroup$ – user6818 May 8 '15 at 17:20
8
$\begingroup$

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.

$\endgroup$
  • $\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$ – user6818 May 8 '15 at 0:16
  • $\begingroup$ Right, all we really need is that $L$ not be decidable in exponential time. $\endgroup$ – Yuval Filmus May 8 '15 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$ – user6818 May 8 '15 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$ – Yuval Filmus May 8 '15 at 0:39
  • $\begingroup$ But the question is to find a decidable language in $P/poly$ which is not in $P$ ... $\endgroup$ – user6818 May 8 '15 at 0:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.