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 ℓ ∞ /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 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 φ, that generalises certain well-known random graph models, show instances of this distribution for every complexity class, and prove that the set of all φ validating 0-1 law is not recursively enumerable.