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)?

  • $\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, 2015 at 19:57
  • $\begingroup$ Ofcourse $\mathsf{RL}=\mathsf{L}$ implies $\mathsf{RL}$-complete problems exist. However converse is not true. $\endgroup$
    – user34945
    Oct 1, 2015 at 20:04


Your Answer

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