8
$\begingroup$

In the context of descriptive complexity PH is the class of languages expressible by statements of second-order logic. What classes of languages do higher order logics correspond to?

$\endgroup$
  • 2
    $\begingroup$ @EmilJeřábek Please make that an answer! Maybe to you it's obvious, but that's pretty cool. $\endgroup$ – Huck Bennett Nov 11 '19 at 6:11
12
$\begingroup$

As you move to higher-order logics, each new order gives you quantification over exponentially larger objects than before, thus you can simulate exponentially longer computations. Other than that, it works pretty much the same as in the second-order case.

More precisely, define the iterated exponential function $2_d^x$ by $$\begin{align*}2_0^x&=x,\\2_{d+1}^x&=2^{2_d^x}.\end{align*}$$ Let $\Sigma^d_m$ denote in the usual fashion the class of $(d+1)$th order sentences that consist of $m$ alternating blocks of $(d+1)$th order quantifiers starting from existential, followed by a $d$th order formula. (Note that the superscript is off by one from the order. Don’t blame me for this historical peculiarity.)

Then:

  • For any $d,m\ge1$, the class of all $\Sigma^d_m$-expressible languages is exactly $\Sigma_m\text-\mathrm{TIME}\bigl(2_{d-1}^{\mathrm{poly}(n)}\bigr)$.

  • Thus, for any $d\ge1$, the languages expressible in $(d+1)$th order logic are exactly those from the $2_{d-1}^x$-time hierarchy: $\bigcup_m\Sigma_m\text-\mathrm{TIME}\bigl(2_{d-1}^{\mathrm{poly}(n)}\bigr)$. For example, second-order logic corresponds to $\mathrm{PH}$, and third-order logic to $\mathrm{EXPH}$.

  • Thus, the class of languages expressible in all of finite-order logic is $\mathrm{ELEMENTARY}$.

Reference:

[1] Leszek Kołodziejczyk: Truth definitions in finite models, Journal of Symbolic Logic 69 (2004), no. 1, pp. 183–200, doi: 10.2178/jsl/1080938836.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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