What are semantic classes that have a syntactic equivalent?

Question

This question is related to 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?

Answer 1

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, 2000.

[2] Emil Jeřábek, Approximate counting in bounded arithmetic, Journal of Symbolic Logic 72 (2007), no. 3, pp. 959–993. doi, preprint

Answer 2

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, arXiv link)

• $\mathsf{MIP} = \mathsf{NEXP}$ (Babai-Fortnow-Lund)

• The PCP Theorem $\mathsf{NP} = \mathsf{PCP}[\log n, O(1)]$ (Arora-Safra, Arora-Lund-Motwani-Sudan-Szegedy)

Answer 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" by Lange.

Answer 4

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.