3
$\begingroup$

Are there number theoretic problems (such as those related to $\mathsf{gcd}$) that are in $\mathsf{RL}$?

Can these also be $\mathsf{RL}$-complete problems (is there any $\mathsf{RL}$-complete problem at all)?

$\endgroup$
  • $\begingroup$ (Well, if $\: \mathsf{RL} \in \{\hspace{-0.02 in}\mathsf{L},\hspace{-0.03 in}\mathsf{NL}\hspace{-0.02 in}\} \:$ then there are $\mathsf{RL}$-complete problems.) $\;\;\;\;$ $\endgroup$ – user6973 Oct 1 '15 at 19:57
  • $\begingroup$ Ofcourse $\mathsf{RL}=\mathsf{L}$ implies $\mathsf{RL}$-complete problems exist. However converse is not true. $\endgroup$ – user34945 Oct 1 '15 at 20:04

Your Answer

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