2
$\begingroup$

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

$\endgroup$

1 Answer 1

5
$\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$.

$\endgroup$
2
  • 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, 2020 at 19:26
  • $\begingroup$ @Ariel You're right, fixed! $\endgroup$ Jun 11, 2020 at 21:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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