Descriptive model theory uses logic to characterize complexity classes

How to model

  1. Counting Hierarchy

in descriptive model theory?


1 Answer 1


This is only a partial answer (to the $PSPACE$ characterization), but I don't have the reputation to comment.

$PSPACE$ has the following (equivalent) descriptive characterizations:

  1. $FO[2^{n^{O(1)}}]$, first-order logic with exponentially iterated quantifier blocks.
  2. $SO[n^{O(1)}]$, second-order logic with polynomially iterated quantifier blocks.
  3. $SO[TC]$, second-order logic with a transitive closure operator.
  4. $FO[PFP]$, first-order logic with a partial fixed point operator.
  5. $CRAM$-$PROC[2^{n^{O(1)}}, n^{O(1)}]$, concurrent-read concurrent-write random access machine with exponential time and polynomial hardware.
  6. $CRAM$-$PROC[n^{O(1)}, 2^{n^{O(1)}}]$, concurrent-read concurrent-write with polynomial time and exponential hardware.

These are all mentioned in Immerman's book Descriptive Complexity.

I can't find a reference on a descriptive characterization for the counting hierarchy, but here are some observations:

  • $PP$ naturally corresponds to existential second-order logic with a second-order majority quantifier.

  • $TC^0$ is equal to $FO$ with a majority quantifier. Padding arguments give us a relationship between $TC^0$ and $CH$. This relationship makes $SO$ with a majority quantifier (on relations) a natural candidate for a descriptive characterization of $CH$.

  • 1
    $\begingroup$ It should, however, be mentioned that characterisations 1 and 4 only hold for properties of ordered structures. But for example not for graphs. E.g., whether an graph without edges has an even number of nodes cannot be expressed in FO[PFP]. 2 and 3 should work, though. $\endgroup$
    – Thomas S
    Jun 28, 2017 at 20:39
  • $\begingroup$ @SamMcGuire Then $\oplus P$ is existential $SO$ logic with $SO$ parity quantifier? $\endgroup$
    – Turbo
    Mar 7, 2019 at 13:04

Your Answer

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