Finding Relations in Polynomial Time

Abstract

Given a set of m observations on n variables, an O(mn2 ) algorithm is proposed to find a basis of all affine relations between these variables satisfied by the observations. On a 25 variables example, this new algorithm is 130 000 times faster than the "all subsets" option for linear regression of the SAS package which is a non polynomial alternative. Extension to the cases where squares, ratios, products of pairs of variables or logarithms of such terms appear in the relations is straightforward and remains polynomial. The method is first tested with data for several classical discoveries studied previously by the Bacon programs. Then it is added to the AutoGraphiX system for computer-aided graph theory thus making it entirely automated. To demonstrate the power of the resulting system, five novel relations (or conjectures) in graph theory are found, two of which pertain to mathematical chemistry. Three conjectures involve five invariants, which is more than in most propositions of graph theory. Proofs of two conjectures are also given.