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