Random lattices and a conjectured 0 - 1 law about their polynomial time computable properties

Abstract

We formulate a conjecture about random n-dimensional lattices with a suitable distribution. The conjecture says that every polynomial time computable property of a random lattice holds with a probability either close to 0 or close to 1. Accepting the conjecture we get a large class of hard lattice problems. We describe an analogy between our conjecture and a set theoretical axiom, which cannot be proved in ZFC. This axiom says that there exists a nontrivial σ-additive 0 - 1 measure defined on the set of all subsets of some set S.