7
$\begingroup$

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?

$\endgroup$
  • 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 Grochow Mar 9 '18 at 16:39
  • $\begingroup$ Another example is ReachUL. See this paper. $\endgroup$ – William Hoza Mar 11 '18 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$ – domotorp Mar 11 '18 at 6:43
  • $\begingroup$ @domotorp Oops. Done. $\endgroup$ – William Hoza Mar 13 '18 at 5:14
9
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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:

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.