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?
$\begingroup$
$\endgroup$
4
-
2$\begingroup$ Does MIP=NEXP count? Or is it too closely related to IP=PSPACE to count as another example? Also QIP=PSPACE? $\endgroup$– Joshua GrochowMar 9, 2018 at 16:39
-
$\begingroup$ Another example is ReachUL. See this paper. $\endgroup$– William HozaMar 11, 2018 at 5:43
-
2$\begingroup$ @William I suggest you turn this into an answer with a link that doesn't require a U Texas account... $\endgroup$– domotorpMar 11, 2018 at 6:43
-
$\begingroup$ @domotorp Oops. Done. $\endgroup$– William HozaMar 13, 2018 at 5:14
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
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
answered Mar 9, 2018 at 8:58
$\begingroup$
$\endgroup$
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)
answered Mar 9, 2018 at 22:03
$\begingroup$
$\endgroup$
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.
$\begingroup$
$\endgroup$
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.
answered Mar 11, 2018 at 17:51