First order complexity of finite random structures

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 classical 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.