Descriptive model theory uses logic to characterize complexity classes
How to model
- Counting Hierarchy
- PSPACE
in descriptive model theory?
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this communityThis 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:
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$.