  We introduce a restricted second-order logic $\mathrm{SO}^{\mathit{plog}}$
for finite structures where second-order quantification ranges over relations
of size at most poly-logarithmic in the size of the structure. We demonstrate
the relevance of this logic and complexity class by several problems in
database theory. We then prove a Fagin's style theorem showing that the Boolean
queries which can be expressed in the existential fragment of
$\mathrm{SO}^{\mathit{plog}}$ corresponds exactly to the class of decision
problems that can be computed by a non-deterministic Turing machine with random
access to the input in time $O((\log n)^k)$ for some $k \ge 0$, i.e., to the
class of problems computable in non-deterministic poly-logarithmic time. It
should be noted that unlike Fagin's theorem which proves that the existential
fragment of second-order logic captures NP over arbitrary finite structures,
our result only holds over ordered finite structures, since
$\mathrm{SO}^{\mathit{plog}}$ is too weak as to define a total order of the
domain. Nevertheless $\mathrm{SO}^{\mathit{plog}}$ provides natural levels of
expressibility within poly-logarithmic space in a way which is closely related
to how second-order logic provides natural levels of expressibility within
polynomial space. Indeed, we show an exact correspondence between the
quantifier prefix classes of $\mathrm{SO}^{\mathit{plog}}$ and the levels of
the non-deterministic poly-logarithmic time hierarchy, analogous to the
correspondence between the quantifier prefix classes of second-order logic and
the polynomial-time hierarchy. Our work closely relates to the constant depth
quasipolynomial size AND/OR circuits and corresponding restricted second-order
logic defined by David A. Mix Barrington in 1992. We explore this relationship
in detail.
