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.
Citation:
Miklós Ajtai, "Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties," focs, pp.733, The 43rd Annual IEEE Symposium on Foundations of Computer Science (FOCS'02), 2002 Usage of this product signifies your acceptance of the Terms of Use. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||