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?


1 Answer 1


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)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.