An unambiguous class possessing a complete set

1. R. Aleliunas, R. Karp, R. Lipton, L. Lovasz, and C. Rackoff. Random walks, universal sequences and the complexity of maze problems. In Proc. of 20rd FOCS, pages 218–223, 1979.

   Google Scholar 

2. E. Allender and K.-J. Lange. StUSPACE(log n) in DSPACE(log² n/loglog n). In Proc. of the 17th ISAAC, 1996. In print.

   Google Scholar 

3. C. Bennet. Time/Space trade-offs for reversible computation. SIAM J. Comp., 18:766–776, 1989.

   Article  Google Scholar 

4. G. Buntrock, B. Jenner, K.-J. Lange, and P. Rossmanith. Unambiguity and fewness for logarithmic space. In Proc. of the 8th Conference on Fundamentals of Computation Theory, number 529 in LNCS, pages 168–179, 1991.

   Google Scholar 

5. Ka Wong Chong and Tak Wah Lam. Finding connected components in O(log n log log n) time on the EREW PRAM. In Proceedings of the Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pages 11–20, 1993.

   Google Scholar 

6. S. Cook. Deterministic CFLs are accepted simultaneously in polynomial time and log squared space. In Proc. of the 11th Annual ACM Symp. on Theory of Computing, pages 338–345, 1979.

   Google Scholar 

7. S. Cook. A taxonomy of problems with fast parallel algorithms. Inform. and Control, 64:2–22, 1985.

   Article  Google Scholar 

8. P. Dymond and W. Ruzzo. Parallel RAMs with owned global memory and deterministic context-free language recoginition. In Proc. of 13th International Colloquium on Automata, Languages and Programming, number 26 in LNCS, pages 95–104. Springer, 1986.

   Google Scholar 

9. M. Fellows and N. Koblitz. Self-witnessing polynomial-time complexity and prime factorization. In Proc. of the 7th IEEE Structure in Complexity Conference, pages 107–110, 1992.

   Google Scholar 

10. J. Hartmanis and L. Hemachandra. Complexity classes without machines: on complete languages for UP. Theoret. Comput. Sci., 58:129–142, 1988.

    Article  Google Scholar 

11. N. Immerman. Nondeterministic space is closed under complementation. SIAM J. Comp., 17:935–938, 1988.

    Article  Google Scholar 

12. M. Karchmer and A. Wigderson. On span programs. In Proc. of the 8th IEEE Structure in Complexity Theory Conference, pages 102–111, 1993.

    Google Scholar 

13. W. Kowalczyk. Some connections between present ability of complexity classes and the power of formal systems of reasoning. In Proc. of 10th Symposium on Mathematical Foundations of Computer Science, number 201 in LNCS, pages 364–368. Springer, 1984.

    Google Scholar 

14. P. Lewis and C.H. Papadimitriou. Symmetric space-bounded computation. Theoret. Comput. Sci., 19:161–187, 1982.

    Article  Google Scholar 

15. G. Miller. Riemann's hypothesis and tests for primality. J. Comp. System Sci., 13:300–317, 1976.

    Google Scholar 

16. N. Nisan. RL ⊂-SC. In Proc. of the 24th Annual ACM Symposium on Theory of Computing, pages 619–623, 1992.

    Google Scholar 

17. N. Nisan, E. Szemeredi, and A. Wigderson. Undirected connectivity in O(log 1.5 n) space. In Proc. of 33th Annual IEEE Symposium on Foundations of Computer Science, pages 24–29, 1992.

    Google Scholar 

18. M. Saks and S. Zhou. RSPACE(s) ⊂-DSPACE(s3/2). In Proc. of 36th FOCS, pages 344–353, 1995.

    Google Scholar 

19. R. Szelepcsényi. The method of forcing for nondeterministic automata. Acta Information, 26:279–284, 1988.

    Article  Google Scholar 

20. A. Wigderson. NL/poly ⊂-⊕L/poly. In Proc. of the 9th IEEE Structure in Complexity Conference, pages 59–62, 1994.

    Google Scholar 

Download references