It is well-known that directed st-connectivity is $NL$-complete. Reingold's breakthrough result showed that undirected st-connectivity is in $L$. Planar directed st-connectivity is known to be in $UL \cap coUL$. Cho and Huynh defined a parametrized knapsack problem and exhibited a hierarchy of problems between $L$ and $NL$.
I am looking for more problems that are intermediate between $L$ and $NL$ i.e., problems that are :
- known to be in $NL$ but not known (or unlikely) to be $NL$-complete and
- known to be $L$-hard but not known to be in $L$.