  For a sequence of random structures with $n$-element domains over a
relational signature, we define its first order (FO) complexity as a certain
subset in the Banach space $\ell^{\infty}/c_0$. The well-known FO zero-one law
and FO convergence law correspond to FO complexities equal to $\{0,1\}$ and a
subset of $\mathbb{R}$, respectively. We present a hierarchy of FO complexity
classes, introduce a stochastic FO reduction that allows to transfer complexity
results between different random structures, and deduce using this tool several
new logical limit laws for binomial random structures. Finally, we introduce a
conditional distribution on graphs, subject to a FO sentence $\varphi$, that
generalises certain well-known random graph models, show instances of this
distribution for every complexity class, and prove that the set of all
$\varphi$ validating 0--1 law is not recursively enumerable.
