Relationships among P L , # L , and the determinant

Eric Allender; Mitsunori Ogihara

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (1996)

  • Volume: 30, Issue: 1, page 1-21
  • ISSN: 0988-3754

How to cite

top

Allender, Eric, and Ogihara, Mitsunori. "Relationships among $PL$, $\#L$, and the determinant." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 30.1 (1996): 1-21. <http://eudml.org/doc/92523>.

@article{Allender1996,
author = {Allender, Eric, Ogihara, Mitsunori},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {nondeterministic logspace-bounded machine; reducibility},
language = {eng},
number = {1},
pages = {1-21},
publisher = {EDP-Sciences},
title = {Relationships among $PL$, $\#L$, and the determinant},
url = {http://eudml.org/doc/92523},
volume = {30},
year = {1996},
}

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
PB - EDP-Sciences
VL - 30
IS - 1
SP - 1
EP - 21
LA - eng
KW - nondeterministic logspace-bounded machine; reducibility
UR - http://eudml.org/doc/92523
ER -

References

top
  1. 1. E. ALLENDER, Oracles vs Proof techniques that do not relativize, Proc. SIGAL International Symposium on Algorithms, Lecture Notes in Computer Science, 1990, 450, pp. 39-52. MR1081954
  2. 2. E. ALLENDER, R. BEALS and M. OGIHARA, The complexity of matrix rank and feasible systems of linear equations, to appear in Proc. 28th STOC, 1996. Zbl0937.65150MR1724603
  3. 3. E. ALLENDER and J. JIAO, Depth reduction for noncommutative arithmetic circuits, Proc. 25th STOC, 1993, pp. 515-522. Zbl1310.68097
  4. 4. C. ÀLVAREZ, J. BALCÁZAR and B. JENNER, Adaptive logspace reducibility and parallel time, Mathematical Systems Theory, 1995, 28, pp. 117-140. Zbl0815.68054MR1303563
  5. 5. C. ÀLVAREZ and B. JENNER, A very hard log-space counting class, Theoretical Computer Science, 1993, 107, pp. 3-30. Zbl0813.68098MR1201163
  6. 6. J. BALCÁZAR, Adaptive logspace and depth-bounded reducibilities, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 240-254. 
  7. 7. S. BERKOWITZ, On computing the determinant in small parallel time using a small number of processors, Information Processing Letters, 1984, 18, pp. 147-150. Zbl0541.68019MR760366
  8. 8. A. BORODIN, S. COOK and N. PIPPENGER, Parallel computation for well-endowed rings and space-bounded probabilistic machines, Information and Control, 1983, 48, pp. 113-136. Zbl0598.68043MR750405
  9. 9. A. BORODIN, S. COOK, P. DYMOND, W. RUZZO and M. TOMPA, Two applications of inductive counting for complementation problems, SIAM Journal on Computing, 1989, 18, pp. 559-578. Zbl0678.68031MR996836
  10. 10. S. BUSS, S. COOK, A. GUPTA and V. RAMACHANDRAN, An optimal parallel algorithm for formula evaluation, SIAM Journal on Computing, 1992, 21, pp. 755-780. Zbl0825.68424MR1171860
  11. 11. A. BEN-DOR and S. HALEVI, Zero-one permanent is #P-complete, a simpler proof, Proc. 2nd Israel Symposium on Theory of Computing and Systems (ISTCS93), IEEE press. 
  12. 12. D. BARRINGTON, N. IMMERMAN and H. STRAUBING, On uniformity within NC1, Journal of Computer and System Sciences, 1990, 41, pp. 274-306. Zbl0719.68023MR1079468
  13. 13. R. BEIGEL, N. REINGOLD and D. SPIELMAN, PP is closed under intersection, Journal of Computer and System Sciences, 1995, 50, pp. 191-202. Zbl0827.68040MR1330252
  14. 14. G. BUNTROCK, C. DAMM, U. HERTRAMPF and C. MEINEL, Structure and Importance of Logspace MOD-Classes, Mathematical Systems Theory, 1992, 25, pp. 223-237. Zbl0749.68033MR1151340
  15. 15. S. COOK, A taxonomy of problems with fast parallel algorithms, Information and Control, 1985, 64, pp. 2-22. Zbl0575.68045MR837088
  16. 16. C. DAMM, DET = L#L?, Informatik-Preprint 8, Fachbereich Informatik der Humboldt-Universität zu Berlin, 1991. 
  17. 17. S. FENNER, L. FORTNOW and S. KURTZ, Gap-definable counting classes, Journal of Computer and System Sciences, 1994, 48, pp. 116-148. Zbl0802.68051MR1259653
  18. 18. L. FORTNOW and N. REINGOLD, PP is closed under truth-table reductions, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 13-15. Zbl0851.68029
  19. 19. J. GILL, Computational complexity of probabilistic Turing machines, SIAM Journal on Computing, 1977, 6, pp. 675-695. Zbl0366.02024MR464691
  20. 20. J. GILL, J. HUNT and J. SIMON, Deterministic simulation of tape-bounded probabilistic Turing machine transducers, Theoretical Computer Science, 1980, 12, pp. 333-338. Zbl0442.68034MR589314
  21. 21. F. GREEN, J. KÖBLER, K. REGAN, T. SCHWENTICK and J. TORÁN, The power of the middle bit of a #P function, to appear in Journal of Computer and System Sciences. Zbl0849.68036MR1339555
  22. 22. S. GUPTA, 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. 23. D. ISAACSON and R. MADSEN, Markov Chains, Theory and Applications, Wiley and Sons, 1976. Zbl0332.60043MR407991
  24. 24. B. JENNER, personal communication. 
  25. 25. H. JUNG, Relationships between probabilistic and deterministic tape complexity, Proc. 10th MFCS, Lecture Notes in Computer Science, 1981, 118, pp. 339-346. Zbl0462.68031MR652767
  26. 26. H. JUNG, On probabilistic tape complexity and fast circuits for matrix inversion problems, Proc, 11th ICALP, Lecture Notes in Computer Science, 1984, 172, pp. 281-291. Zbl0583.68024MR784256
  27. 27. H. JUNG, On probabilistic time and space, Proc. 12th ICALP, Lecture Notes in Computer Science, 1985, 194, pp. 310-317. Zbl0599.68043MR819266
  28. 28. H. JUNG, Stochastische Turingmaschinen und die Kompliziertheit arithmetischer Probleme, doctoral dissertation, Humboldt-Universität, East Berlin. 
  29. 29. R. LADNER and N. LYNCH, Relativization of questions about log space computability, Mathematical Systems Theory, 1976, 10, pp. 19-32. Zbl0341.68036MR419190
  30. 30. R. LADNER, N. LYNCH and A. SELMAN, A comparison of polynomial-time reducibilities, Theoretical Computer Science, 1975, 1, pp. 103-123. Zbl0321.68039MR395319
  31. 31. I. MACARIE, Space-efficient deterministic simulation of probabilistic automata, Proc. 11th STACS, Lecture Notes in Computer Science, 1994, 775, pp. 109-122. 
  32. 32. I. MACARIE, 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. 33. N. NISAN, RL ⊆ SC, Computational Complexity, 1994, 4, pp. 1-11. Zbl0806.68043MR1272773
  34. 34. M. OGIHARA, NCk(NP) = ACk-1(NP), Proc. 11th STACS, Lecture Notes in Computer Science, 1994, 775, pp. 313-324. MR1288548
  35. 35. M. OGIHARA, The PL Hierarchy collapses, to appear in Proc. 28th STOC, 1996. Zbl0922.68054MR1427501
  36. 36. M. OGIWARA and L. HEMACHANDRA, A complexity theory for feasible closure properties, Journal of Computer and System Sciences, 1993, 46, pp. 295-325. Zbl0798.68060MR1228809
  37. 37. K. REGAN and T. SCHWENTICK, 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]. MR1254503
  38. 38. P. ROSSMANITH, personal communication. 
  39. 39. W. RUZZO, J. SIMON and M. TOMPA, Space-bounded hierarchies and probabilistic computation, Journal of Computer and System Sciences, 1984, 28, pp. 216-230. Zbl0573.68021MR760544
  40. 40. S. SALUJA, A note on the permanent problem, Information Processing Letters, 1992, 43, pp. 1-5. Zbl0780.68067MR1179752
  41. 41. J. SIMON, On tape-bounded probabilistic Turing machine acceptors, Theoretical Computer Science, 1981, 16, pp. 158-167. Zbl0473.68044MR632672
  42. 42. J. SIMON, Space-bounded probabilistic Turing machine complexity classes are closed under complement, Proc. 13th STOC, 1981, pp. 158-167. 
  43. 43. J. SIMON, J. GILL and J. HUNT, On tape-bounded probabilistic Turing machine transducers, Proc. 19th FOCS, 1978, pp. 107-112. 
  44. 44. S. TODA, 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. 45. S. TODA, Classes of arithmetic circuits capturing the complexity of computing the determinant, IEICE Trans. Inf. and Syst., 1992, vol. E75-D, pp. 116-124. 
  46. 46. J. TORÁN, Complexity classes defined by counting quantifiers, Journal of the ACM, 1991, 38, pp. 753-774. Zbl0799.68080MR1125929
  47. 47. L. VALIANT, The complexity of computing the Permanent, Theoretical Computer Science, 1979, 8, pp. 189-201. Zbl0415.68008MR526203
  48. 48. L. VALIANT, 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. Zbl0769.68050MR1211869
  49. 49. V. VINAY, Counting auxiliary pushdown automata and semi-unbounded arithmetic circuits, Proc. 6th IEEE Structure in Complexity Theory Conference, 1991, pp. 270-284. 
  50. 50. K. WAGNER, The complexity of combinatorial problems with succinct input representation, Acta Informatica, 1986, 23, pp. 325-356. Zbl0621.68032MR853581
  51. 51. C. WILSON, Relativized NC, Mathematical Systems Theory, 1987, 20, pp. 13-29. Zbl0627.68043MR901891
  52. 52. C. B. WILSON, Decomposing NC and AC, SIAM Journal on Computing, 1990, 19, pp. 384-396. Zbl0692.68045MR1042734
  53. 53. V. ZANKÓ, #P-completeness via many-one reductions, International Journal of Foundations of Computer Science, 1991, 2, pp. 77-82. Zbl0739.68036MR1122511
  54. 54. D. ZUCKERMAN, personal communication. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.