After Omer Reingold's famous proof (from 2005?) that SL = L, the distinction between natural L complete problems and natural SL complete problems has been mostly dropped, so that it became difficult for me to find examples of natural L complete problems. (Here "difficult" means article behind paywall and google book with limited number of shown pages.)
The typical natural L complete problem should be complete for L under AC0 many-one reductions, and the proof that it is in L should not use (or reveal) SL = L. Take this list:
- undirected graph acyclicity
- undirected graph accessibility problem (UGAP)
- undirected s-t connectivity (USTCONN)
- directed tree s-t connectivity
- tree isomorphism
- product of two permutations for disjoint cycle representation
(I believe that all problems in this list are L complete, but I don't know which are natural. I know that UGAP=USTCONN is not natural. I guess that both undirected graph acyclicity and directed tree s-t connectivity are natural. I am unsure whether tree isomorphism and product of two permutations are complete under AC0 many-one reductions, but at least I know that showing they are in L does not reveal SL = L.)
How can I learn more about the natural L complete problems on the above list? Are there other interesting L complete problems missing on the above list?
My motivation for looking for L complete problem is the question of the relation between NC1 and L. After learning that L ⊆ EREW1 (and the hint that directed tree s-t connectivity should be L complete), my suspicion that NC1 = L got quite strong, since NC1 ⊆ L and NC1 ≈ EREW1 (one is logarithmic time in uniform circuit model, the other is logarithmic time in the weak exclusive read/exclusive write PRAM model).