On non-linear lower bounds in computational complexity

ABSTRACT

The purpose of this paper is to explore the possibility that purely graph-theoretic reasons may account for the superlinear complexity of wide classes of computational problems. The results are therefore of two kinds: reductions to graph theoretic conjectures on the one hand, and graph theoretic results on the other. We show that the graph of any algorithm for any one of a number of arithmetic problems (e.g. polynomial multiplication, discrete Fourier transforms, matrix multiplication) must have properties closely related to concentration networks.

REFERENCES

• 1: Aho, A.V., Hirschberg, D.S. and Ullman, J.D. Bounds on the Complexity of the longest subsequence problem. Proc. 15th Symp. on SWAT 104-109, (1974).
• 2: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 3: Borodin, A. and Munro, I. Computational Complexity of Algebraic and Numeric Problems. American Elsevier. (1975).
• 4: Cook, S.A. and Reckhow, R. A. Time bounded random access machines. JCSS 7, 354-375, (1973).
• 5: M. J. Fischer , M. S. Paterson, STRING-MATCHING AND OTHER PRODUCTS, Massachusetts Institute of Technology, Cambridge, MA, 1974
• 6: Fischer, M.J. and Pippinger, N. To appear.
• 7: Floyd, R.W. Permuting information in idealized two-level storage. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (eds.), Plenum Press (1972).
• 8: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 9: Morris, J.H. and Pratt, V.R. A linear pattern-matching algorithm. TR-40, Computer Center, University of California at Berkeley (1970).
• 10: Pinsker, M.S. On the complexity of a concentrator. 7th International Teletraffic Congress, Stockholm. (1973).
• 11: Pippenger, N. The complexity theory of switching networks. Technical Report 487, Res. Lab. of Electronics, MIT, (1973).
• 12: John E. Savage, The Complexity of Computing, Krieger Publishing Co., Inc., Melbourne, FL, 1987
• 13: Strassen, V. Die Berechnungkomplexitat von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten. Numer. Math 20, (1973).
• 14: Valiant, L.G. Parallelism in comparison problems. SIAM J. on Computing, (to appear).
• 15: Robert A. Wagner , Michael J. Fischer, The String-to-String Correction Problem, Journal of the ACM (JACM), v.21 n.1, p.168-173, Jan. 1974 [doi>10.1145/321796.321811]
• 16: Abraham Waksman, A Permutation Network, Journal of the ACM (JACM), v.15 n.1, p.159-163, Jan. 1968 [doi>10.1145/321439.321449]
• 17: Yao, F.F. personal communication.
• 18: Yao, A.C.-C., and Yao, F.F. Lower bounds on merging networks. Manuscript (1974).

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Bounded-action devices (e.g., Turing machines, random access machines)

General Terms:
Algorithms, Theory