Relationships among $PL$, $\#L$, and the determinant

Abstract

Valiant have shown that the complexity of the determinant is characterized by the complexity ofeounting the number ofaccepting computations ofa nondeterministic logspace-bounded machine. (This class of fonctions is known as #L.) By using that characterization and by establishing a few elementary closure properties, 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.