I know that $R/Poly$ solves the halting problem, as we can have the program that runs for longest time as advice and check which halts earlier. But what if we weaken the $R$ into something, like $PR$?

  • 1
    $\begingroup$ Can you define PR/poly and the halting problem? The exact definitions might matter. $\endgroup$ – Yuval Filmus Dec 28 '19 at 16:04

Your Answer

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

Browse other questions tagged or ask your own question.