The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02)
Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties
Vancouver, BC, Canada
November 16-November 19
ISBN: 0-7695-1822-2
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 probabiltiy 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 \sigma -additive 0 - 1 measure defined on the set of all subsets of some set S.