Graph isomorphism is low for PP

1. L. Babai, Moderately exponential bound for graph isomorphism. In Proceedings Fundamentals of Computation Theory, Lecture Notes in Computer Science 117 (1981), 34–50.

   Google Scholar 

2. L. Babai, S. Moran, Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. In Journal of Computer and System Sciences 36 (1988), 254–276.

   Google Scholar 

3. J.L. Balcázar, J. Díaz, J. Gabarró, Structural Complexity I. Springer, 1987.

   Google Scholar 

4. R. Beigel, J. Gill, U. Hertrampf, Counting classes: Thresholds, parity, mods, and fewness. In Proceedings 7th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 415 (1990), 49–57.

   Google Scholar 

5. R. Beigel, L. Hemachandra, G. Wechsung, On the power of probabilistic polynomial time: PNP[log] ⊂-PP. In Proceedings 4th Structure in Complexity Theory Conference, p. 225–227, IEEE Computer Society, 1989.

   Google Scholar 

6. R. Boppana, J. Hastad, and S. Zachos, Does co-NP have short interactive proofs? In Information Processing Letters 25 (1987), 127–132.

   Google Scholar 

7. J. Cai, L.A. Hemachandra, On the power of parity. In Proceedings 6th Symposium on Theoretical Aspects of Computer Science, Lecture Notes in Computer Science 349 (1989), 229–240.

   Google Scholar 

8. S.A. Cook, The complexity of theorem-proving procedures. In Proceedings of the 3rd ACM Symposium on Theory of Computing 1971, 151–158.

   Google Scholar 

9. S. Even, A. Selman Y. Yacobi, The complexity of promise problems with applications to public-key cryptography. In Information and Control 61 (1984), 114–133.

   Google Scholar 

10. S. Fenner, L. Fortnow, S. Kurtz, Gap-definable counting classes. In Proceedings of the 6th Structure in Complexity Theory Conference 1991, 30–42.

    Google Scholar 

11. M. Furst, J. Hopcroft, E. Luks, Polynomial time algorithms for permutation groups. In Proceedings of the 21st ACM Symposium on Theory of Computing 1980, 36–41.

    Google Scholar 

12. M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Freeman, San Francisco, 1979.

    Google Scholar 

13. J. Gill, Computational complexity of probabilistic Turing machines. In SIAM Journal on Computing 6 (1977), 675–695.

    Google Scholar 

14. O. Goldreich, S. Micali, and A. Wigderson, Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. In Proceedings of the 27th Symposium on Foundations of Computer Science 1986, 174–187.

    Google Scholar 

15. S. Goldwasser, S. Micali, and C. Rackoff, The knowledge complexity of interactive proofs. In Proceedings of the 17th ACM Symposium on the Theory of Computing 1985, 291–304.

    Google Scholar 

16. S. Goldwasser, M. Sipser, Private coins versus public coins in interactive proof systems. In Proceedings of the 18th ACM Symposium on the Theory of Computing 1986, 59–68.

    Google Scholar 

17. F. Green, On the Power of Deterministic Reductions to C=P. Technical Report LSI-91-14 Universidad Politecnica de Catalunya, 1991.

    Google Scholar 

18. M. Hall, The Theory of Groups, Macmillan, New York, 1959.

    Google Scholar 

19. C. Hoffmann, Group-Theoretic Algorithms and Graph Isomorphism, Springer-Verlag Lecture Notes in Computer Science #136, 1982.

    Google Scholar 

20. C. Hoffmann, Subcomplete generalizations of graph isomorphism. In Journal of Computer and System Sciences 25 (1982), 332–359.

    Google Scholar 

21. D.S. Johnson, The NP-completeness column: An ongoing guide. In Journal of Algorithms 6 (1985), 434–451.

    Google Scholar 

22. D. Kratsch, L.A. Hemachandra, On the complexity of graph reconstruction. In Fundamentals of Computing Theory 1991, to appear.

    Google Scholar 

23. J. Köbler, U. Schöning, J. Torán and S. Toda, Turing Machines with few accepting computations and low sets for PP. In Proceedings of the 4th Structure in Complexity Theory Conference 1989, 208–216.

    Google Scholar 

24. E. Luks, Isomorphism of Graphs of Bounded Valence can be tested in Polynomial Time. In Journal of Computer and System Sciences 25 (1982), 42–65.

    Google Scholar 

25. R. Mathon, A note on the graph isomorphism counting problem. In Inform. Process. Lett. 8 (1979), 131–132.

    Google Scholar 

26. M. Ogiwara, L. Hemachandra, A complexity theory for closure properties. In Proceedings of the 6th Structure in Complexity Theory Conference 1991, 16–29.

    Google Scholar 

27. C. Papadimitriou, S. Zachos Two remarks on the power of counting. In 6th GI Conference on Theoretical Computer Science, Lecture Notes in Computer Science 145 (1983) 269–276.

    Google Scholar 

28. U. Schöning, Complexity and Structure. Springer-Verlag Lecture Notes in Computer Science 211, 1986.

    Google Scholar 

29. U. Schöning, Graph isomorphism is in the low hierarchy. In Journal of Computer and System Sciences 37 (1988), 312–323.

    Google Scholar 

30. J. Simon, On some central problems in computational complexity. Ph.D. Thesis, Cornell University (1975).

    Google Scholar 

31. C. Sims, Computation with permutation groups. In Proceedings of the 2nd ACM Symposium on Symbolic and Algebraic Manipulations 1971, 23–28.

    Google Scholar 

32. J. Tarui, Degree complexity of boolean functions and its applications to relativized separations. In Proceedings of the 6th Structure in Complexity Theory Conference 1991, 382–390.

    Google Scholar 

33. S. Toda, On the computational power of PP and ⊕P. In Proceedings of the 30th Symposium on Foundations of Computer Science 1989, 514–519.

    Google Scholar 

34. S. Toda, Private communication.

    Google Scholar 

35. J. Torán, An oracle characterization of the Counting Hierarchy. In Proceedings of the 3rd Structure in Complexity Theory Conference 1988, 213–224.

    Google Scholar 

36. L.G. Valiant, The relative complexity of checking and evaluating. In Information Processing Letters 5 (1976), 20–23.

    Google Scholar 

37. L.G. Valiant, The complexity of computing the permanent. In Theoretical Computer Science 8 (1979), 189–201.

    Google Scholar 

38. L.G. Valiant V.V Vazirani, NP is as easy as detecting unique solutions In Theoretical Computer Science 47 (1986), 85–93.

    Google Scholar 

39. K.W. Wagner, The complexity of combinatorial problems with succinct input representation. In Acta Informatica 23 (1986), 325–356.

    Google Scholar 

Download references