Some independence results in complexity theoryFootnote^†

^†This research was supported in part by NSF Grants MCS8102853 and MCS8304756.

References

• Aho , A. , Hopcroft , J. and Ullman , J. 1974 . The Design and Analysis of Computer Algorithms , Reading, MA : Addison-Wesley .
   Google Scholar
• Fischer , M. and Meyer , A. 1971 . Boolean matrix multiplication and transitive closure . Proceedings of the 12th Symposium on Switching and Automata Theory . 1971 . pp. 129 – 131 .
   Google Scholar
• Ibarra , O. and Moran , S. 1981 . Deterministic and probabilistic algorithms for maximum bipartite matching via fast matrix multiplication . Information Processing Letters , 13 : 12 – 15 .
   Google Scholar
• Ibarra , O. and Moran , S. On the power of control statements in reducing the number of operations needed to compute algebraic functions , 81 – 10 . University of Minnesota . Department of Computer Science, TR
   Google Scholar
• Ibarra , O. , Moran , S. and Hui , R. 1982 . A generalization of the fast LUP matrix decomposition algorithm and applications . Journal of Algorithms , 3 : 45 – 56 .
   Google Scholar
• Rudin , W. 1970 . Real and Complex Analysis , New York : McGraw-Hill .
   Google Scholar
• Strassen , V. 1973 . Berechnung und Programm II . Ana Informatica , 2 : 64 – 79 .
   Google Scholar
• Strassen , V. 1969 . Gaussian elimination is not optimal . Numer. Math , 13
   Google Scholar