<p>Let <span class="math-container">${\cal L}=\{Y_1,..., Y_k, X\}$</span> be a finite relational language such that <span class="math-container">$X$</span> is a unary relation name. Let <span class="math-container">$\phi(X,\bar{Y})\in{\cal L}$</span> be a first-order formula (the formula can have the equality relation). For a natural number <span class="math-container">$n$</span>, we have <span class="math-container">$$([n],X')\models \exists \bar{Y}\phi(X,\bar{Y})$$</span> when <span class="math-container">$X$</span> is interpreted by <span class="math-container">$X'\subseteq [n]$</span> iff there exists an expansion <span class="math-container">$([n],X',\bar{Y'})$</span> of <span class="math-container">$([n],X')$</span> such that <span class="math-container">$$([n],X',\bar{Y'})\models \phi(X,\bar{Y}).$$</span></p>
<p>A language <span class="math-container">$L\subseteq \{0,1\}^*$</span> is <span class="math-container">$\Sigma^1_1$</span>-definable using the relation names in <span class="math-container">$\cal L$</span> over finite domains iff there exists a formula <span class="math-container">$\phi(X,\bar{Y})\in{\cal L}$</span> such that for every <span class="math-container">$x\in \{0,1\}^*$</span>,</p>
<ul>
<li><span class="math-container">$x\in L$</span></li>
</ul>
<p>if and only if</p>
<ul>
<li><span class="math-container">$([|x|],S_x)\models \exists \bar{Y}\phi(X,\bar{Y})$</span> where <span class="math-container">$S_x=\{i\in [|x|]:x_i=1\}$</span>.</li>
</ul>
<p>So for example the majority language <span class="math-container">${\bf Maj}=\{x\in\{0,1\}^*: x\text{ has at least }\lfloor\frac{|x|}{2}\rfloor \text{ ones.}\}$</span> is <span class="math-container">$\Sigma^1_1$</span>-definable. Let <span class="math-container">${\cal L}=\{X(.),Y(.,.)\}$</span> be our language, then <span class="math-container">$\phi_{Maj}(X,Y)$</span> is the conjunction of the following formulas:</p>
<ol>
<li><span class="math-container">$\forall i \exists j(\neg X(i)\to X(j)\land Y(i,j))$</span>.</li>
<li><span class="math-container">$\forall i,j,k(i\neq j\to \neg(Y(i,k)\land Y(j,k)))$</span>.</li>
</ol>
<p>Other interesting symmetric languages can be defined in this way. Moreover, it is possible to allow <span class="math-container">$X$</span> to have more arity to define more complicated languages.</p>
<p>My question is the following:</p>
<blockquote>
<p>Does the class of languages that are <span class="math-container">$\Sigma^1_1$</span>-definable in this terminology have a Computational complexity name?</p>
</blockquote>
<p>The important property here is that we do not use interpreted relations such as linear order in <span class="math-container">$\phi(X,\bar{Y})$</span> (except the equality).</p>

CC BY-SA 4.0
2021-01-15T08:28:24.647Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-01-15T09:22:33.493Z
@EmilJeřábek  You are right. I was hoping to get a more restricted syntactic characterization. For example, can't we say something like that this class is the symmetric $\exists A$ languages or symmetric Nondeterministic $A$ languages where $A$ is $DLOGTIME$ for example? The important point for me is the syntactic characterization and not the semantic characterization which is symmetric $NP$ as you mentioned.
Erfan Khaniki
CC BY-SA 4.0
2021-01-15T10:10:10.417Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-01-15T11:14:18.510Z
Note that even without no symmetry conditions, $\mathrm{NP=\exists coNLOGTIME}$, whereas $\mathrm{\exists DLOGTIME=\exists NLOGTIME=NLOGTIME}$ does not include e.g. Majority.
Emil Jeřábek
CC BY-SA 4.0
2021-01-15T19:25:16.280Z
@EmilJeřábek, I see. Thanks a lot for your comments.
Erfan Khaniki
CC BY-SA 4.0
2021-01-21T10:56:34.737Z
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.
Emil Jeřábek
CC BY-SA 4.0
2021-01-21T12:33:02.770Z
(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 https://cstheory.stackexchange.com/a/48136 .
Emil Jeřábek
CC BY-SA 4.0
2021-01-21T13:47:09.683Z
@EmilJeřábek. Thanks a lot for your new comments and the reference. I really appreciate it.
Erfan Khaniki
<cc.complexity-theory><lo.logic><terminology><descriptive-complexity><finite-model-theory>
Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains
Erfan Khaniki
# Complexity class name for the class of languages that are $\Sigma^1_1$-definable over finite domains

(Asked by: username_0 on 2021-01-14)

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).

**Tags:** cc.complexity-theory, lo.logic, terminology, descriptive-complexity, finite-model-theory
> **Comments:**
> **username_1**: 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.  
> **username_0**: @EmilJeřábek  You are right. I was hoping to get a more restricted syntactic characterization. For example, can't we say something like that this class is the symmetric $\exists A$ languages or symmetric Nondeterministic $A$ languages where $A$ is $DLOGTIME$ for example? The important point for me is the syntactic characterization and not the semantic characterization which is symmetric $NP$ as you mentioned.  
> **username_1**: 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.  
> **username_1**: Note that even without no symmetry conditions, $\mathrm{NP=\exists coNLOGTIME}$, whereas $\mathrm{\exists DLOGTIME=\exists NLOGTIME=NLOGTIME}$ does not include e.g. Majority.  
> **username_0**: @EmilJeřábek, I see. Thanks a lot for your comments.  
> **username_1**: 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.  
> **username_1**: (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 https://cstheory.stackexchange.com/a/48136 .  
> **username_0**: @EmilJeřábek. Thanks a lot for your new comments and the reference. I really appreciate it.  

---

## 0 answers

