1
$\begingroup$

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

Improve this question
$\endgroup$
8
  • 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$
    – Emil Jeřábek
    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$
    – Emil Jeřábek
    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$
    – Emil Jeřábek
    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$
    – Emil Jeřábek
    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$
    – Emil Jeřábek
    Jan 21, 2021 at 12:33

0

Reset to default

Your Answer

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