# Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains

Let $${\cal L}=\{Y_1,..., Y_k, X\}$$ be a finite relational language such that $$X$$ is a unary relation name. Let $$\phi(X,\bar{Y})\in{\cal L}$$ be a first-order formula (the formula can have the equality relation). For a natural number $$n$$, we have $$([n],X')\models \exists \bar{Y}\phi(X,\bar{Y})$$ when $$X$$ is interpreted by $$X'\subseteq [n]$$ iff there exists an expansion $$([n],X',\bar{Y'})$$ of $$([n],X')$$ such that $$([n],X',\bar{Y'})\models \phi(X,\bar{Y}).$$

A language $$L\subseteq \{0,1\}^*$$ is $$\Sigma^1_1$$-definable using the relation names in $$\cal L$$ over finite domains iff there exists a formula $$\phi(X,\bar{Y})\in{\cal L}$$ such that for every $$x\in \{0,1\}^*$$,

• $$x\in L$$

if and only if

• $$([|x|],S_x)\models \exists \bar{Y}\phi(X,\bar{Y})$$ where $$S_x=\{i\in [|x|]:x_i=1\}$$.

So for example the majority language $${\bf Maj}=\{x\in\{0,1\}^*: x\text{ has at least }\lfloor\frac{|x|}{2}\rfloor \text{ ones.}\}$$ is $$\Sigma^1_1$$-definable. Let $${\cal L}=\{X(.),Y(.,.)\}$$ be our language, then $$\phi_{Maj}(X,Y)$$ is the conjunction of the following formulas:

1. $$\forall i \exists j(\neg X(i)\to X(j)\land Y(i,j))$$.
2. $$\forall i,j,k(i\neq j\to \neg(Y(i,k)\land Y(j,k)))$$.

Other interesting symmetric languages can be defined in this way. Moreover, it is possible to allow $$X$$ to have more arity to define more complicated languages.

My question is the following:

Does the class of languages that are $$\Sigma^1_1$$-definable in this terminology have a Computational complexity name?

The important property here is that we do not use interpreted relations such as linear order in $$\phi(X,\bar{Y})$$ (except the equality).

• These are exactly the symmetric NP languages. Just take a $\Sigma^1_1$ definition of the language with a linear order, and then existentially quantify the ordering relation away; the symmetry of the language guarantees that the new formula still defines the same language. Commented Jan 15, 2021 at 8:28
• I’m not quite sure what you mean, but this class consists exactly of languages of the form $L=\{w\in\{0,1\}^*:(\#_0(w),\#_1(w))\in L'\}$ for $L'\in\mathrm{NE}$, where $\#_i(w)$ is the number of occurrences of symbol $i$ in word $w$. Thus, they are as easy or as difficult to characterize as arbitrary $\mathrm{NE}$ languages. Commented Jan 15, 2021 at 10:10
• Note that even without no symmetry conditions, $\mathrm{NP=\exists coNLOGTIME}$, whereas $\mathrm{\exists DLOGTIME=\exists NLOGTIME=NLOGTIME}$ does not include e.g. Majority. Commented Jan 15, 2021 at 11:14
• On second thoughts, I don’t recall where I’ve seen the $\mathrm{\exists DLOGTIME=NLOGTIME}$ claim and I can’t reconstruct the argument, so I may have misremembered it. In any case, using the fact that a DLOGTIME machine can only access $O(\log n)$ bits of the existential witness, it is easy to show at least that $\mathrm{\exists NLOGTIME=\exists DLOGTIME\subseteq\Sigma_2\text-TIME}(\log n)\subseteq\mathrm{AC}^0$ and $\mathrm{\exists DLOGTIME\subseteq NTIME}\bigl((\log n)^3\bigr)$. Either way, it does not include Majority. Commented Jan 21, 2021 at 10:56
• (Sorry for the increasingly more and more off-topic comments.) One can improve this a little to $\mathrm{\exists DLOGTIME\subseteq NTIME}\bigl((\log n)^2\log\log n\bigr)$ (with $O(\log n\log\log n)$ nondeterministic steps), using a representation of the partial witness by a decision tree with $O(\log n)$ nodes (which can be described with $O(\log n\log\log n)$ bits) as in cstheory.stackexchange.com/a/48136 . Commented Jan 21, 2021 at 12:33