@article{ITA_1996__30_1_1_0,
author = {Allender, Eric and Ogihara, Mitsunori},
title = {Relationships among $PL$, $\#L$, and the determinant},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {1--21},
publisher = {EDP-Sciences},
volume = {30},
number = {1},
year = {1996},
mrnumber = {1398856},
zbl = {0851.68033},
language = {en},
url = {http://www.numdam.org/item/ITA_1996__30_1_1_0/}
}
TY - JOUR AU - Allender, Eric AU - Ogihara, Mitsunori TI - Relationships among $PL$, $\#L$, and the determinant JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 1996 SP - 1 EP - 21 VL - 30 IS - 1 PB - EDP-Sciences UR - http://www.numdam.org/item/ITA_1996__30_1_1_0/ LA - en ID - ITA_1996__30_1_1_0 ER -
%0 Journal Article %A Allender, Eric %A Ogihara, Mitsunori %T Relationships among $PL$, $\#L$, and the determinant %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 1996 %P 1-21 %V 30 %N 1 %I EDP-Sciences %U http://www.numdam.org/item/ITA_1996__30_1_1_0/ %G en %F ITA_1996__30_1_1_0
Allender, Eric; Ogihara, Mitsunori. Relationships among $PL$, $\#L$, and the determinant. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 30 (1996) no. 1, pp. 1-21. http://www.numdam.org/item/ITA_1996__30_1_1_0/
1. , Oracles vs Proof techniques that do not relativize, Proc. SIGAL International Symposium on Algorithms, Lecture Notes in Computer Science, 1990, 450, pp. 39-52. | MR
2. , and , The complexity of matrix rank and feasible systems of linear equations, to appear in Proc. 28th STOC, 1996. | MR | Zbl
3. and , Depth reduction for noncommutative arithmetic circuits, Proc. 25th STOC, 1993, pp. 515-522.
4. , and , Adaptive logspace reducibility and parallel time, Mathematical Systems Theory, 1995, 28, pp. 117-140. | MR | Zbl
5. and , A very hard log-space counting class, Theoretical Computer Science, 1993, 107, pp. 3-30. | MR | Zbl
6. , Adaptive logspace and depth-bounded reducibilities, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 240-254.
7. , On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, 1984, 18, pp. 147-150. | MR | Zbl
8. , and , Parallel computation for well-endowed rings and space-bounded probabilistic machines, Information and Control, 1983, 48, pp. 113-136. | MR | Zbl
9. , , , and , Two applications of inductive counting for complementation problems, SIAM Journal on Computing, 1989, 18, pp. 559-578. | MR | Zbl
10. , , and , An optimal parallel algorithm for formula evaluation, SIAM Journal on Computing, 1992, 21, pp. 755-780. | MR | Zbl
11. and , Zero-one permanent is #P-complete, a simpler proof, Proc. 2nd Israel Symposium on Theory of Computing and Systems (ISTCS93), IEEE press.
12. , and , On uniformity within NC1, Journal of Computer and System Sciences, 1990, 41, pp. 274-306. | MR | Zbl
13. , and , PP is closed under intersection, Journal of Computer and System Sciences, 1995, 50, pp. 191-202. | MR | Zbl
14. , , and , Structure and Importance of Logspace MOD-Classes, Mathematical Systems Theory, 1992, 25, pp. 223-237. | MR | Zbl
15. , A taxonomy of problems with fast parallel algorithms, Information and Control, 1985, 64, pp. 2-22. | MR | Zbl
16. , DET = L#L?, Informatik-Preprint 8, Fachbereich Informatik der Humboldt-Universität zu Berlin, 1991.
17. , and , Gap-definable counting classes, Journal of Computer and System Sciences, 1994, 48, pp. 116-148. | MR | Zbl
18. and , PP is closed under truth-table reductions, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 13-15. | Zbl
19. , Computational complexity of probabilistic Turing machines, SIAM Journal on Computing, 1977, 6, pp. 675-695. | MR | Zbl
20. , and , Deterministic simulation of tape-bounded probabilistic Turing machine transducers, Theoretical Computer Science, 1980, 12, pp. 333-338. | MR | Zbl
21. , , , and , The power of the middle bit of a #P function, to appear in Journal of Computer and System Sciences. | MR | Zbl
22. , The power of witness reduction, to appear in SIAM Journal on Computing. A preliminary version appeared in Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 43-59.
23. and , Markov Chains, Theory and Applications, Wiley and Sons, 1976. | MR | Zbl
24. , personal communication.
25. , Relationships between probabilistic and deterministic tape complexity, Proc. 10th MFCS, Lecture Notes in Computer Science, 1981, 118, pp. 339-346. | MR | Zbl
26. , On probabilistic tape complexity and fast circuits for matrix inversion problems, Proc, 11th ICALP, Lecture Notes in Computer Science, 1984, 172, pp. 281-291. | MR | Zbl
27. , On probabilistic time and space, Proc. 12th ICALP, Lecture Notes in Computer Science, 1985, 194, pp. 310-317. | MR | Zbl
28. , Stochastische Turingmaschinen und die Kompliziertheit arithmetischer Probleme, doctoral dissertation, Humboldt-Universität, East Berlin.
29. and , Relativization of questions about log space computability, Mathematical Systems Theory, 1976, 10, pp. 19-32. | MR | Zbl
30. , and , A comparison of polynomial-time reducibilities, Theoretical Computer Science, 1975, 1, pp. 103-123. | MR | Zbl
31. , Space-efficient deterministic simulation of probabilistic automata, Proc. 11th STACS, Lecture Notes in Computer Science, 1994, 775, pp. 109-122.
32. , Space-bounded probabilistic computation: old and new stories, SIGACT News Complexity Theory Column 10 (edited by Lane Hemaspaandra), SIGACT News, 1995, 26, number 3, September, pp. 2-12.
33. , RL ⊆ SC, Computational Complexity, 1994, 4, pp. 1-11. | MR | Zbl
34. , NCk(NP) = ACk-1(NP), Proc. 11th STACS, Lecture Notes in Computer Science, 1994, 775, pp. 313-324. | MR
35. , The PL Hierarchy collapses, to appear in Proc. 28th STOC, 1996. | MR
36. and , A complexity theory for feasible closure properties, Journal of Computer and System Sciences, 1993, 46, pp. 295-325. | MR | Zbl
37. and , On the power of one bit of a #P-function, Proc. 4th Italian Conference on Theoretical Computer Science, World Scientific Press, Singapore, 1992, pp. 317-329. See also [21]. | MR
38. , personal communication.
39. , and , Space-bounded hierarchies and probabilistic computation, Journal of Computer and System Sciences, 1984, 28, pp. 216-230. | MR | Zbl
40. , A note on the permanent problem, Information Processing Letters, 1992, 43, pp. 1-5. | MR | Zbl
41. , On tape-bounded probabilistic Turing machine acceptors, Theoretical Computer Science, 1981, 16, pp. 158-167. | MR | Zbl
42. , Space-bounded probabilistic Turing machine complexity classes are closed under complement, Proc. 13th STOC, 1981, pp. 158-167.
43. , and , On tape-bounded probabilistic Turing machine transducers, Proc. 19th FOCS, 1978, pp. 107-112.
44. , Counting problems computationally equivalent to the determinant, Technical Report CSIM 91-07, Dept. Comp. Sci. and Inf. Math., Univ. of Electro-Communications, Tokyo, 1991.
45. , Classes of arithmetic circuits capturing the complexity of computing the determinant, IEICE Trans. Inf. and Syst., 1992, vol. E75-D, pp. 116-124.
46. , Complexity classes defined by counting quantifiers, Journal of the ACM, 1991, 38, pp. 753-774. | MR | Zbl
47. , The complexity of computing the Permanent, Theoretical Computer Science, 1979, 8, pp. 189-201. | MR | Zbl
48. , Why is Boolean complexity theory difficult? in Boolean Function Complexity, edited by M. S. Paterson, London Mathematical Society Lecture Notes, Series 169, Cambridge University Press, 1992. | MR | Zbl
49. , Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 270-284.
50. , The complexity of combinatorial problems with succinct input representation, Acta Informatica, 1986, 23, pp. 325-356. | MR | Zbl
51. , Relativized NC, Mathematical Systems Theory, 1987, 20, pp. 13-29. | MR | Zbl
52. , Decomposing NC and AC, SIAM Journal on Computing, 1990, 19, pp. 384-396. | MR | Zbl
53. , #P-completeness via many-one reductions, International Journal of Foundations of Computer Science, 1991, 2, pp. 77-82. | MR | Zbl
54. , personal communication.
