Relationships among PL, #L, and the determinant
- 17 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 267-278
- https://doi.org/10.1109/sct.1994.315797
Abstract
Results by Toda (1991), Vinay (1991), Damm (1991), and Valiant (1992) 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.) By using that characterization and by establishing a few elementary closure properties, we give a very simple proof of a theorem of Jung (1985), 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.Keywords
This publication has 35 references indexed in Scilit:
- The Power of the Middle Bit of a #P FunctionJournal of Computer and System Sciences, 1995
- Space-efficient deterministic simulation of probabilistic automataPublished by Springer Nature ,1994
- A complexity theory for feasible closure propertiesJournal of Computer and System Sciences, 1993
- Depth reduction for noncommutative arithmetic circuitsPublished by Association for Computing Machinery (ACM) ,1993
- A note on the permanent value problemInformation Processing Letters, 1992
- Space-bounded hierarchies and probabilistic computationsJournal of Computer and System Sciences, 1984
- On tape-bounded probabilistic Turing machine acceptorsTheoretical Computer Science, 1981
- Space-bounded probabilistic turing machine complexity classes are closed under complement (Preliminary Version)Published by Association for Computing Machinery (ACM) ,1981
- Relativization of questions about log space computabilityTheory of Computing Systems, 1976
- A comparison of polynomial time reducibilitiesTheoretical Computer Science, 1975