On the complexity of functions for random access machines

ABSTRACT

Tight bounds are proved for Sort, Merge, Insert, Gcd of integers, Gcd of polynomials, and Rational functions over a finite inputs domain, in a random access machine with arithmetic operations, direct and indirect addressing, unlimited power for answering YES/NO questions, branching, and tables with bounded size. These bounds are also true even if additions, subtractions, multiplications, and divisions of elements by elements of the field are not counted. In a random access machine with finitely many constants and a bounded number of types of instructions, it is proved that the complexity of a function over a countable infinite domain is equal to the complexity of the function in a sufficiently large finite subdomain.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Michael Ben-Or, Lower bounds for algebraic computation trees, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.80-86, December 1983 [doi>10.1145/800061.808735]
• 3: ~BSHOUTY, N.H. Euclid's GCD algorithm is not optimal. I. Upper bounds. In preparation.
• 4: ~BSHOUTY, N.H. Euclid's GCD algorithm is not optimal, II. Lower bounds. In preparation.
• 5: ~FRIEDMAN, N. Some results on the effect of arithmetics on comparison problems. In ~Proceedings of the 13th IEEE Symposium on Switching and Automata Theory. IEEE, New York, ~1972, pp. 139-143.
• 6: ~HONG, J. On lower bounds of time complexity of some algorithms. Scienna Sinica 22 (1979), ~890-900.
• 7: ~KAMINSKI, M., AND BSHOUTY, N.H. Multiplicative complexity of polynomial multiplication ~over finite field. In Proceedmgs of the 28th Amzual Symposium on Foundations of Computer ~Science. IEEE, New York, 1987.
• 8: ~MANSOUR, Y., SCHIEBER, B., AND TIWARI, P. Lower bounds for greatest common divisor ~computation. In Proceedings of the 29th 1EEE Symposium on Foundations of Computer Science ~(Oct.), IEEE, New York, 1988, pp. 54-63,
• 9: Friedhelm Meyer auf der Heide, Lower bounds for solving linear diophantine equations on random access machines, Journal of the ACM (JACM), v.32 n.4, p.929-937, Oct. 1985 [doi>10.1145/4221.4250]
• 10: Shlomo Moran , Marc Snir , Udi Manber, Applications of Ramsey's theorem to decision tree complexity, Journal of the ACM (JACM), v.32 n.4, p.938-949, Oct. 1985 [doi>10.1145/4221.4259]
• 11: ~PAUL, W., AND SIMON, J. Decision trees and random access machines. In Monographie 30, ~L'Enseignement Mathematique, Logic and Algorithmic--An International Symposmm Held in ~Honor of Ernst Specker. Univ. Geneva Press, Geneva, Switzerland, 1982, pp. 331-340~
• 12: J. T. Schwartz, Fast Probabilistic Algorithms for Verification of Polynomial Identities, Journal of the ACM (JACM), v.27 n.4, p.701-717, Oct. 1980 [doi>10.1145/322217.322225]
• 13: ~STRASSEN, g. Die Berechnungskomplexitat von elementarsymmetrischen funktionen und ~von Interpolationskoeffizienten. Numer. Math 20 (1973), 238-251.
• 14: ~YAO, A. Lower bounds for algebraic computation trees with integer inputs. In Proceedings of ~the 30th IEEE Symposium on Foundations of Computer Science, IEEE, New York, 1989.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

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)
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Theory, Verification

Keywords:
greatest common divisor, indirect addressing, random access machine, sorting