Determining equivalence of expressions in random polynomial time

ABSTRACT

We devise several procedures based on signatures (or hashing functions) to determine equivalence of expressions in Random Polynomial Time (also called Probabilistic Polynomial Time) (RPT). These procedures return as result: “equivalent” or “not-equivalent”. The result “not-equivalent” is always correct, while the result “equivalent” is correct with probability at least 1-&egr;. This probability depends on a random number generator and is independent of the problem being solved. In all our procedures, the value &egr; can be made arbitrarily small. This method works for determining equivalence over an important class of functions as well as answering other questions like linearity, polynomial dependence, squareness, independence, etc.

REFERENCES

• 1: Edmonds, J.: Systems of Distinct Representatives and Linear Algebra; Journal of Research of the NBS, 71B(4):241-245, (Dec 1967).
• 2: Hardy, G.H. and Wright, E.M.: The Theory of Numbers; Oxford Clarendon Press, Fourth Ed, (1975)
• 3: Heintz, J. and Schnorr, C.P.: Testing Polynomials which are easy to compute; Proceedings of An International Symposium Held in Honour of Ernst Specker; Monographie 30 de l'enseignement Mathematique; 237-254, (Feb 1980)
• 4: Ibarra, O.H., Moran, S. and Rosier, L.E.: Probabilistic Algorithms and Straight-Line Programs for Some Rank Decision Problems; Inf Proc Letters, 12(5):227-232, (Oct 1981)
• 5: Oscar H. Ibarra , Shlomo Moran, Probabilistic Algorithms for Deciding Equivalence of Straight-Line Programs, Journal of the ACM (JACM), v.30 n.1, p.217-228, Jan. 1983 [doi>10.1145/322358.322373]
• 6: William A. Martin, Determining the Equivalence of Algebraic Expressions by Hash Coding, Journal of the ACM (JACM), v.18 n.4, p.549-558, Oct. 1971 [doi>10.1145/321662.321668]
• 7: Joel Moses, Algebraic simplification: a guide for the perplexed, Communications of the ACM, v.14 n.8, p.527-537, Aug. 1971 [doi>10.1145/362637.362648]
• 8: Rabin, M.O.: Probabilistic Algorithms; in Algorithms and Complexity, Academic Press, New York, (1976).
• 9: Rabin, M.O.: Probabilistic Algorithms in Finite Fields; Siam J Computing, 9(2):273-280, (May 1980)
• 10: 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]
• 11: Solovay, R. and Strassen, V.: A Fast Monte-Carlo Test for Primality; SIAM J Computing; 6:84-85, (1977).
• 12: Welsh, D.J.A.: Randomised Algorithms; Discrete Mathematics, 133-145, (1983).
• 13: Richard Zippel, Probabilistic algorithms for sparse polynomials, Proceedings of the International Symposiumon on Symbolic and Algebraic Computation, p.216-226, June 01, 1979

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.1 Expressions and Their Representation
          Subjects: Simplification of expressions

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Number-theoretic computations (e.g., factoring, primality testing)

  G. Mathematics of Computing
  G.3 PROBABILITY AND STATISTICS
      Subjects: Random number generation; Probabilistic algorithms (including Monte Carlo)

General Terms:
Algorithms, Theory