The complexity of the equivalence problem for straight-line programs

ABSTRACT

We look at several classes of straight-line programs and show that the equivalence problem is either undecidable or computationally intractable for all but the trivial classes. For example, there is no algorithm to determine if an arbitrary program (with positive, negative, or zero integer inputs) using only constructs x ← 1, x ← x + y, x ← x/y (integer division) outputs 0 for all inputs. The result holds even if we consider only programs which compute total 0/1 - functions. For programs using constructs x ← 0, x ← c, x ← cx, x ← x/c, x ← x + y, x ← x − y, skip l, if p(x) then skip l, and halt,1 the equivalence problem is decidable in [equation] time (&lgr; is a fixed positive constant and N is the maximum of the sizes of the programs). The bound cannot be reduced to a polynomial in N unless P &equil; NP. In fact, we prove the following rather surprising result: The equivalence problem for programs with one input/output variable and one intermediate variable using only constructs x ← x + y and x ← x/2 is NP-hard. We also show the decidability of the equivalence problem for a certain class of programs and use this result to prove the following: Let IN be the set of natural numbers and f be any total one-to-one function from IN onto IN × IN. (f is called a pair generator. Such functions are useful in recursive function and computability theory.) Then f cannot be computed by any program using only constructs x ← 0, x ← c, x ← x + y, x ← x − y, x ← x * y, x ← x/y, skip l, if p(x) then skip l, and halt.

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: A. V. Aho , S. C. Johnson, Optimal code generation for expression trees, Proceedings of seventh annual ACM symposium on Theory of computing, p.207-217, May 05-07, 1975, Albuquerque, New Mexico, United States [doi>10.1145/800116.803770]
• 3: Aho, A.V. and Ullman, J.D., Optimization of straight line programs, SIAM J. Computing, 1, 1 (March 1972), pp. 1–19.
• 4: John Bruno , Ravi Sethi, Code Generation for a One-Register Machine, Journal of the ACM (JACM), v.23 n.3, p.502-510, July 1976 [doi>10.1145/321958.321971]
• 5: Constable, R.L., Hunt, H.B., and Sahni, S., On the computational complexity of scheme equivalence, Proc. Eight Annual Princeton Conference on Information Sciences and Systems (1974), pp. 15–20.
• 6: Stephen A. Cook, The complexity of theorem-proving procedures, Proceedings of the third annual ACM symposium on Theory of computing, p.151-158, May 03-05, 1971, Shaker Heights, Ohio, United States [doi>10.1145/800157.805047]
• 7: Davis, M., “Computability and Unsolvability,” McGraw-Hill, New York, 1958.
• 8: Davis, M., Matijasevič, Y., and Robinson, J., Hilbert's tenth problem. Diophantine equations: Positive aspects of a negative solution, Proc. of Symposium on Pure Mathematics, 28 (1976), pp. 323–378.
• 9: Fred C. Hennie, Introduction to Computability, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1977
• 10: John E. Hopcroft , Jeffrey D. Ullman, Introduction To Automata Theory, Languages, And Computation, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 11: Karp, R.M., Reducibility among combinatorial problems, in “ Complexity of Computer Computations,” R.E. Miller and J.W. Thatcher, Eds., Plenum Press, New York, 1972, pp. 85–104.
• 12: Donald E. Knuth, The art of computer programming, volume 2 (3rd ed.): seminumerical algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1997
• 13: Albert R. Meyer , Dennis M. Ritchie, The complexity of loop programs, Proceedings of the 1967 22nd national conference, p.465-469, January 1967, Washington, D.C., United States [doi>10.1145/800196.806014]
• 14: Marvin Lee Minsky, Computation: Finite and Infinite Machines, Prentice-Hall, Inc., Upper Saddle River, NJ, 1967
• 15: Hartley Rogers, Jr., Theory of recursive functions and effective computability, MIT Press, Cambridge, MA, 1987
• 16: Sahni, S., Computationally related problems, SIAM J. Computing 3 (1974), pp. 262–279.
• 17: Ravi Sethi , J. D. Ullman, The Generation of Optimal Code for Arithmetic Expressions, Journal of the ACM (JACM), v.17 n.4, p.715-728, Oct. 1970 [doi>10.1145/321607.321620]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Computability theory

General Terms:
Theory