Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR02-061 | 14th November 2002 00:00

A conjectured 0-1 law about the polynomial time computable properties of random lattices, I.


Authors: Miklos Ajtai
Publication: 18th November 2002 12:23
Downloads: 3941


A measure $\mu_{n}$ on $n$-dimensional lattices with
determinant $1$ was introduced about fifty years ago to prove the
existence of lattices which contain points from certain sets. $\mu_{n}$
is the unique probability measure on lattices with determinant $1$ which
is invariant under linear transformations with determinant $1$, where a
linear transformation acts on a lattice point by point. Our main goal
is to formulate a conjectured $0-1$ law about $\mu_{n}$. In the second
part of the paper we will also give a method for generating a random
lattice with the distribution $\mu_{n}$. As we will see, there are many
known and proven $0-1$ laws concerning random structrues, but they are
valid for a much smaller set of properties, e.g. first-order definable
properties. The infinite sequence $\langle P_{n}\ |\ $, $n=1,2,\ldots
\rangle $ is a property of lattices if for each $n$, $P_{n}$ is a set of
$n$-dimensional lattices with determinant $1$. We say that a property
$P_{n}$, $n=1,2,\ldots $ is polynomial time computable (p.t.c.) if there
is a probabilistic Turing machine $T$ so that given a lattice with {\it
any} basis as an input $T$ decides with high probability in polynomial
time whether $P_{n}$ holds. The conjecture states that for any p.t.c.
property if the integer $n$ is sufficiently large then the probability
$\mu_{n}(P_{n})$ is either close to $0$ or close to $1$. More precisely
we have $\lim_{n \rightarrow\infty}\max \lbrace
\mu_{n}(P_{n}),\mu_{n}(\neg P_{n}) \rbrace =1$. The conjecture implies
$P\not= NP$ so there is not much hope for proving it, but it gives a way
to create a large number of hard lattice problems. (E.g. it implies
that for any fixed set $H$ of volume $1$ in $\err^{n}$ it cannot be
decided in polynomial time whether a lattice contains a nonzero point
from $H$.) We do not think that there is any reason to belive that it
is easier to prove $P\not=NP$ through the conjecture than in any other
way. Our goal is rather to give a way to create a large collection of
computationally hard problems (by accepting a single statement.) As we
will show some of these problems may be useful for cryptographic

ISSN 1433-8092 | Imprint