Lower bounds for solving linear diophantine equations on random access machines

ABSTRACT

The problem of recognizing the language Ln(Ln, k) of solvable Diophantine linear equations with n variables (and solutions from {O, … , k}n) is considered. The languages ∪n&egr;N Ln, ∪n&egr;N Ln, l, the knapsack problem, are NP-complete. The &OHgr;(n2 lower bound for Ln,1 on linear search algorithms due to Dobkin and Lipton is generalized to an &OHgr;(n2log(k + 1)) lower bound for Ln, k. The method of Klein and Meyer auf der Heide is further improved to carry over the &OHgr;(n2) lower bound for Ln, 1 to random access machines (RAMS) in such a way that it holds for a large class of problems and for very small input sets. By this method, lower bounds that depend on the input size, as is necessary for Ln, are proved. Thereby, an &OHgr;(n2log(k + 1)) lower bound is obtained for RAMS recognizing Ln or Ln, k, for inputs from {0, … , (nk)0(n2)}n.

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: BLASCHKE, W.Uber den gr6Bten Kreis in einer konvexen Punktmenge. Jahresbericht der Deutschen Mathematiker Vereinigung 23 ( 1914), 369-374.
• 4: DOBKIN, D., AND LIPTON, R.A lower bound of ~n2 on linear search programs for the knapsack problem. J. Comput. Syst. Sci. 16 (1975), 417-421.
• 5: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 6: Ravi Kannan, Improved algorithms for integer programming and related lattice problems, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.193-206, December 1983 [doi>10.1145/800061.808749]
• 7: KLEIN, P., AND MEYER AUF DER HEIDE, F. A lower time bound for the knapsack problem on random access machines. Acta Inf. 19 (I983), 385-395.
• 8: LAUTEMANN, C., AND MEYER AUF DER HEIDE, F.Lower time bounds for integer programming with two variables. Inf. Proc. Lett., to appear.
• 9: LENSTRA, H. W.Integer programming with a fixed number of variables. Rep. 81-03, Mathematisch Instituut, Universiteit Amsterdam, Amsterdam, The Netherlands, 1981.
• 10: Friedhelm Meyer auf der Heide, A Polynomial Linear Search Algorithm for the n-Dimensional Knapsack Problem, Journal of the ACM (JACM), v.31 n.3, p.668-676, July 1984 [doi>10.1145/828.322450]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Integer programming

General Terms:
Algorithms, Measurement, Performance, Theory, Verification