2
$\begingroup$

Is P/poly known to be in RE? If yes what other classes is it known to be part of.

$\endgroup$
4
$\begingroup$

$P/poly$ is NOT a subset of $RE$. Specifically, the unary non-halting problem (i.e. given a Turing Machine encoded in unary, does it run forever?) is in $P/poly$ but not $RE$. In fact, every undecidable unary language is in $P/poly$.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ The standard halting problem is in RE (unless you are talking about the $\Pi_2$ complete problem of halting on all inputs). Of course any unary encoding of a language outside $RE$ will do. $\endgroup$ – Ariel Jun 11 at 19:26
  • $\begingroup$ @Ariel You're right, fixed! $\endgroup$ – jmite Jun 11 at 21:42

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.