This paragraph in the wikipedia page of the P vs NP problem tries to explain a characterization of languages in P and those in NP, however this characterization is not very clearly stated.
Indeed, for first order logic they say "the language of a finite structure with a fixed signature including a linear order relation [with a suitable fixed point combinator]"; but it's not clear what this means, and it doesn't seem to be explained further.
For existential second order logic, the article just says "NP is the set of languages expressible in existential second-order logic" without any explanation: what does it mean for a language to be expressible in (existential) second-order logic ?
So my question is
What do these characterizations mean, precisely ?
To answer, you can assume I know what a formal language is, that I know what first order logic and existential second order logic, and that I know some decent amount of model theory. Note that I'm not asking for a proof of the characterization (although if there is a quick one I won't mind seeing it), just for a definition of the characterization.
A word $w$ over a finite alphabet $A$ has an associated (first-order) structure defined as follows. The vocabulary has a binary relation symbol $<$ and unary relation symbols $P_a$ for each letter $a\in A$. The structure associated to $w$ has underlying set $\{1,2,\dots,n\}$ where $n$ is the length of $w$; $<$ is interpreted as the usual ordering of the natural numbers $1,2,\dots,n$; and each $P_a$ is interpreted as the set of those $i\in\{1,2,\dots,n\}$ such that the $i$-th letter in $w$ is $a$.
A language $L$ is said to be expressed by a formula $\phi$ (in some logic) if and only if $L$ is the set of those words $w$ whose associated structure satisfies $\phi$.
EDIT: At the OP's suggestion, I'm putting here the link (originally in a comment) http://web.eecs.umich.edu/~gurevich/Opera/152.pdf to a paper describing various fixed-point operators and the associated logics.