# Operators in descriptive complexity

When we talk about operators in descriptive complexity, are they something like this: for example, if transitive closure operator $TR$ is available, we can use variable $y$ that we define as $TR(x)$ where $x$ is input? or is it something else?

Also, when we say $FO(t(n))$, what does quantifier block being iterated $t(n)$ times mean?

First Part: Let's first define the TR operator (Why do you use $TR$ and not $TC$?) Given a formula $\phi$ with free variables $x_{i_1},\dots,x_{i_{2k}}$ than the string $\psi =TR(x_{i_1},\dots,x_{i_{2k}},\phi)(y_{i_1},\dots,x_{i_{yk}})$ is also a formula. If you now consider an interpretation $\mathcal{I}$ than $\psi$ is true under $\mathcal{I}$ iff $(y_{i_1},\dots,y_{i_{2k}})^{\mathcal{I}}\in R^+$, where $(y_{i_1},\dots,y_{i_{2k}})^{\mathcal{I}}$ is the tuple assigned to $(y_{i_1},\dots,y_{i_{2k}})$ by $\mathcal{I}$, $R$ is the binary Relation on $k$-tuples defined by $\phi$ and $^+$ the transitive closure.

As your input is (only) a structure, your Formula can't have free variables, but of course it can have constants, e.g. $\psi = TR(x_1,x_2,\phi,c_1,c_2)$ where $\phi$ is $x_1 P x_2$.

Let's assume your input ${\mathcal{G}}$ is a graph and two of it's vertices: $(V,E,v_1,v_2)$ ($E$ being a symmetric relation, not a set of pairs). Then $P^{\mathcal{G}} = E = R$ (the $R$ from above). Now $\psi^{\mathcal{G}}$ is true (i.e. your input accepted) iff $v_1$ and $v_2$ belong to the same connected component.

Second part: $t(n)$ is a function of the input size, so if your input has size $n$ the quantifier block is repeated as-is $t(n)$ times, using the same variables in each instance.

Again the example of checking whether there is a path:

$$QB(x,y) = (\forall z: \neg(x = y \vee x E y))\\(\exists z )(\forall u)(\forall v (u = x \wedge v = z) \vee (u = z \wedge v = y)) \\(\forall x: x=u)(\forall y: y=v)$$

This block consists of three parts:

1. Check if there's a short path (length 0 or 1), then "quit".
2. Check if there is an intermediate z.
3. Rename the variables to recurse.

Since $(\forall z \phi)\psi$ is short for $\forall z (\phi\rightarrow\psi)$ the formula $QB(x,y)\exists x\neq x$ is only satisfiable if $\neg(x = y \vee x E y)$ is false, i.e. there is a path of length $1$ or $0$ between $x$ and $y$.

If your input has size $n$, you only need $1+\log_2 n$ recursion levels, i.e. $QB(x,y)^{1+\log_2 n}\exists x\neq x$ tests whether $x$ and $y$ are in the same connected component.

This example is taken from: Expressibility and parallel complexity (Immerman,1989)