Quick links

Relationships among PL, #L, and the Determinant

Report ID:
May 1993
Download Formats:


Recent results by Toda, Vinay, Damm, and Valiant have shown that
the complexity of the determinant is characterized by the complexity
of counting the number of accepting computations of a nondeterministic
logspace-bounded machine. (This class of functions is known as #L.)
Using that characterization, we give a very simple proof of a theorem
of Jung, showing that probabilistic logspace-bounded (PL) machines lose
none of their computational power if they are restricted to run in
polynomial time.
We also present new results comparing and contrasting the classes
of functions reducible to PL, #L, and the determinant, using various
notions of reducibility.

Follow us: Facebook Twitter Linkedin