<p>FWIW, the ostensibly semantic class APP defined in [1] was shown to be syntactic in [2].</p>

<p>[1] Valentine Kabanets, Charles Rackoff, Stephen A. Cook, <em>Efficiently
  approximable real-valued functions</em>, ECCC Report <a href="https://eccc.weizmann.ac.il/eccc-reports/2000/TR00-034/" rel="noreferrer">TR00-034</a>, 2000.</p>

<p>[2] Emil Jeřábek, <em>Approximate counting in bounded arithmetic</em>, Journal of Symbolic Logic 72 (2007), no. 3, pp. 959–993. <a href="https://doi.org/10.2178/jsl/1191333850" rel="noreferrer">doi</a>, <a href="http://math.cas.cz/~jerabek/papers/apx.pdf" rel="noreferrer">preprint</a></p>

CC BY-SA 3.0
2018-03-09T08:58:45.980Z
2018-03-09T08:58:45.980Z
Emil Jeřábek
<p>A few others; related to $\mathsf{IP} = \mathsf{PSPACE}$, but there are enough of them that weren't mentioned in the OQ that I figured it's worth putting them here:</p>

<ul>
<li><p>$\mathsf{QIP} = \mathsf{PSPACE}$ (<a href="https://doi.org/10.1145/2049697.2049704" rel="noreferrer">Jain-Ji-Upadhyay-Watrous</a>, <a href="https://arxiv.org/abs/0907.4737" rel="noreferrer">arXiv link</a>)</p></li>
<li><p>$\mathsf{MIP} = \mathsf{NEXP}$ (<a href="https://doi.org/10.1007/BF01200430" rel="noreferrer">Babai-Fortnow-Lund</a>)</p></li>
<li><p>The PCP Theorem $\mathsf{NP} = \mathsf{PCP}[\log n, O(1)]$ (<a href="https://doi.org/10.1145/273865.273901" rel="noreferrer">Arora-Safra</a>, <a href="https://doi.org/10.1145%2F278298.278306" rel="noreferrer">Arora-Lund-Motwani-Sudan-Szegedy</a>) </p></li>
</ul>

CC BY-SA 3.0
2018-03-09T22:03:16.863Z
2018-03-09T22:03:16.863Z
Joshua Grochow
<p>Another example is $\mathbf{ReachUL}$, the class of languages decidable by nondeterministic log-space Turing machines such that for any input and any configuration, there is at most one sequence of nondeterministic choices leading to that configuration. See <a href="https://link.springer.com/chapter/10.1007/BFb0023471" rel="nofollow noreferrer">"An unambiguous class possessing a complete set"</a> by Lange.</p>

CC BY-SA 3.0
2018-03-13T05:12:59.417Z
2018-03-13T05:12:59.417Z
William Hoza
<p>One of my favorites is $IND[t(n)] = FO[t(n)]$, where $IND[t(n)]$ is the class of problems decidable with an inductive definition which closes in less than or equal to $t(n)$ iterations and $FO[t(n)]$ are the problems decidable using a first order logic sentence with less than or equal to $t(n)$ iterated quantifier blocks.</p>

CC BY-SA 3.0
2018-03-11T17:51:16.137Z
2018-03-11T17:51:16.137Z
Samuel Schlesinger
<p>This question is related to <a href="https://cstheory.stackexchange.com/questions/4792/benefits-for-syntactic-and-semantic-classes">Benefits for syntactic and semantic classes</a>.
As mentioned there, $\mathsf{PSPACE} = \mathsf{IP}$, which can be interpreted as the semantic class $\mathsf{IP}$ obtaining a syntactic definition.
What are other non-trivial examples for "syntacticizing" a class?</p>

CC BY-SA 3.0
2018-03-09T16:39:01.060Z
Does MIP=NEXP count? Or is it too closely related to IP=PSPACE to count as *another* example? Also QIP=PSPACE?
Joshua Grochow
CC BY-SA 3.0
2018-03-11T05:43:36.227Z
Another example is ReachUL. See [this paper](https://link-springer-com.ezproxy.lib.utexas.edu/chapter/10.1007/BFb0023471).
William Hoza
CC BY-SA 3.0
2018-03-11T06:43:46.867Z
@William I suggest you turn this into an answer with a link that doesn't require a U Texas account...
domotorp
CC BY-SA 3.0
2018-03-13T05:14:06.130Z
@domotorp Oops. Done.
William Hoza
<cc.complexity-theory><complexity-classes><big-list>
What are semantic classes that have a syntactic equivalent?
domotorp
# What are semantic classes that have a syntactic equivalent?

(Asked by: username_0 on 2018-03-09)

This question is related to [Benefits for syntactic and semantic classes](https://cstheory.stackexchange.com/questions/4792/benefits-for-syntactic-and-semantic-classes).
As mentioned there, $\mathsf{PSPACE} = \mathsf{IP}$, which can be interpreted as the semantic class $\mathsf{IP}$ obtaining a syntactic definition.
What are other non-trivial examples for "syntacticizing" a class?

**Tags:** cc.complexity-theory, complexity-classes, big-list

> **Comments:**
> **username_1**: Does MIP=NEXP count? Or is it too closely related to IP=PSPACE to count as *another* example? Also QIP=PSPACE?  
> **username_2**: Another example is ReachUL. See [this paper](https://link-springer-com.ezproxy.lib.utexas.edu/chapter/10.1007/BFb0023471).  
> **username_0**: @William I suggest you turn this into an answer with a link that doesn't require a U Texas account...  
> **username_2**: @username_0 Oops. Done.  

---

## 4 answers

### Answer by username_3 on 2018-03-09. Score: 9

FWIW, the ostensibly semantic class APP defined in [1] was shown to be syntactic in [2].

[1] Valentine Kabanets, Charles Rackoff, Stephen A. Cook, *Efficiently
approximable real-valued functions*, ECCC Report [TR00-034](https://eccc.weizmann.ac.il/eccc-reports/2000/TR00-034/), 2000.

[2] username_3, *Approximate counting in bounded arithmetic*, Journal of Symbolic Logic 72 (2007), no. 3, pp. 959–993. [doi](https://doi.org/10.2178/jsl/1191333850), [preprint](http://math.cas.cz/~jerabek/papers/apx.pdf)


---

### Answer by username_1 on 2018-03-09. Score: 5

A few others; related to $\mathsf{IP} = \mathsf{PSPACE}$, but there are enough of them that weren't mentioned in the OQ that I figured it's worth putting them here:

* $\mathsf{QIP} = \mathsf{PSPACE}$ ([Jain-Ji-Upadhyay-Watrous](https://doi.org/10.1145/2049697.2049704), [arXiv link](https://arxiv.org/abs/0907.4737))
* $\mathsf{MIP} = \mathsf{NEXP}$ ([Babai-Fortnow-Lund](https://doi.org/10.1007/BF01200430))
* The PCP Theorem $\mathsf{NP} = \mathsf{PCP}[\log n, O(1)]$ ([Arora-Safra](https://doi.org/10.1145/273865.273901), [Arora-Lund-Motwani-Sudan-Szegedy](https://doi.org/10.1145%2F278298.278306))


---

### Answer by username_2 on 2018-03-13. Score: 3

Another example is $\mathbf{ReachUL}$, the class of languages decidable by nondeterministic log-space Turing machines such that for any input and any configuration, there is at most one sequence of nondeterministic choices leading to that configuration. See ["An unambiguous class possessing a complete set"](https://link.springer.com/chapter/10.1007/BFb0023471) by Lange.


---

### Answer by username_4 on 2018-03-11. Score: 2

One of my favorites is $IND[t(n)] = FO[t(n)]$, where $IND[t(n)]$ is the class of problems decidable with an inductive definition which closes in less than or equal to $t(n)$ iterations and $FO[t(n)]$ are the problems decidable using a first order logic sentence with less than or equal to $t(n)$ iterated quantifier blocks.


---

