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


Your Answer

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

Browse other questions tagged or ask your own question.