What language is in $P/Poly \setminus P$? I was thinking of it by hours but I cannot come with an idea. Please help.


One example is the language $$\{ 1^n : \text{the $n$th Turing machine halts on the empty input}\}.$$ This language has constant size circuits, but isn't computable.

| cite | improve this answer | |
  • $\begingroup$ Ok, what about computable languages in $P/poly \setminus P$? $\endgroup$ – Logic Aug 21 '17 at 21:27
  • $\begingroup$ This is an exercise that you can now complete on your own. The answer will look very similar. $\endgroup$ – Yuval Filmus Aug 21 '17 at 21:30

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.