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

  • 3
    $\begingroup$ 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. $\endgroup$ Commented Jan 15, 2021 at 8:28
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 15, 2021 at 10:10
  • 1
    $\begingroup$ Note that even without no symmetry conditions, $\mathrm{NP=\exists coNLOGTIME}$, whereas $\mathrm{\exists DLOGTIME=\exists NLOGTIME=NLOGTIME}$ does not include e.g. Majority. $\endgroup$ Commented Jan 15, 2021 at 11:14
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jan 21, 2021 at 10:56
  • 1
    $\begingroup$ (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 . $\endgroup$ Commented Jan 21, 2021 at 12:33


Your Answer

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