loading...
Random Lattices and a Conjectured 0 - 1 Law about Their Polynomial Time Computable Properties
The 43rd Annual IEEE Symposium on Fou ...
 This Article 
 
PDF
HTML
 
 Share 
   
 Bibliographic References 
   
 Add to: 
 
Digg
Furl
Spurl
Blink
Simpy
Google
Del.icio.us
Y!MyWeb
 
 Search 
   
Miklós Ajtai, IBM Almaden Research Center
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.


Click here to go to beta feedback form