A conjecture about polynomial time computable lattice-lattice functions

摘要

We formulate a conjecture which describes all of the polynomial time computable (p. t. c. ) functions f with domain(f)=lattice n, range(f) ⊆ lattice m, m ≤ n^c, where latticen is the set of lattices in Rⁿ with determinant 1. A former conjecture, the 0-1-conjecture, of the author states that all 0,1-valued functions defined on latticen are constant almost everywhere. Since the n-dimensional lattices as Abelian groups are pairwise isomorphic we can say that, according to this conjecture, the value of a p. t. c. 0,1-function may depend only on the algebraic structure of the lattice and not on the metric defined on it. The new conjecture generalizes this statement for functions where the value is also a lattice. As a typical example we can think of the function f(L)=L′, where L′ is the dual of L. When both thedomain and the range of the functions are n-dimensional lattices with determinants 1 then, according to the conjecture, every p. c. t. functions are either constant or identical almost everywhere to f(L)=AL, or f(L)=AL′, where A is a suitably chosen linear transformation with determinant one.There is a striking analogy between the new conjecture and theorems describing the uniquely definable functions which assign for each n-dimensional vectorspace an m-dimensional vectorspace. These theorems are closely related to questions about the Axiom of Choice. In this analogy polynomial time computation corresponds to definability (in set theory) and lattices to finite dimensional vectorspaces.