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, privacy policy and cookie policy

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