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

<p>$PSPACE$ has the following (equivalent) descriptive characterizations:</p>

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

<p>These are all mentioned in Immerman's book <em>Descriptive Complexity</em>.</p>

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

<ul>
<li><p>$PP$ naturally corresponds to existential second-order logic with a second-order majority quantifier. </p></li>
<li><p>$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$.</p></li>
</ul>

CC BY-SA 3.0
2017-06-28T20:39:28.603Z
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.
Thomas S
CC BY-SA 4.0
2019-03-07T13:04:30.217Z
@SamMcGuire Then $\oplus P$ is existential $SO$ logic with $SO$ parity quantifier?
Turbo
CC BY-SA 3.0
2017-06-28T03:59:56.793Z
2017-06-28T04:16:25.590Z
2017-06-28T04:16:25.590Z
Sam McGuire
<p>Descriptive model theory uses logic to characterize complexity classes</p>

<p>How to model</p>

<ol>
<li>Counting Hierarchy</li>
<li>PSPACE</li>
</ol>

<p>in descriptive model theory?</p>

<cc.complexity-theory><complexity-classes><descriptive-complexity><finite-model-theory><model-theory>
Descriptive model theory classification of Counting hierarchy
Turbo
# Descriptive model theory classification of Counting hierarchy

(Asked by: username_0 on 2017-06-27)

Descriptive model theory uses logic to characterize complexity classes

How to model

1. Counting Hierarchy
2. PSPACE

in descriptive model theory?

**Tags:** cc.complexity-theory, complexity-classes, descriptive-complexity, finite-model-theory, model-theory

---

## 1 answers

### Answer by username_1 on 2017-06-28. Score: 5

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

> **Comments:**
> **username_2**: 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.  
> **username_0**: @SamMcGuire Then $\oplus P$ is existential $SO$ logic with $SO$ parity quantifier?  

---

