2
$\begingroup$

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

$\endgroup$

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.