# Benefits for syntactic and semantic classes

This is a post separated from Consequences of UP equals NP, and also a follow-up question to Semantic vs. Syntactic Complexity Classes.

In the above post we learned about the semantic and syntactic classes. Briefly stated, when a class can be characterized as a leaf language class $\mathsf{L}[L_1|L_2]$, then a class is syntactic if $L_1 \cup L_2 = \Sigma^*$, that is, accepting language $L_1$ is the complement of rejecting language $L_2$; otherwise we called it a semantic class. One can see that $\mathsf{P}$, $\mathsf{NP}$ and $\mathsf{PP}$ are syntactic classes, while classes like $\mathsf{BPP}$ and $\mathsf{IP}$ are semantic classes.

Classical result like $\mathsf{PSPACE} = \mathsf{IP}$ and conjecture $\mathsf{P} \stackrel{?}{=} \mathsf{BPP}$ both can be view as semantic classes turns out to have syntactic characterizations. It seems to me that the syntactic classes are easier to handle, since they have natural complete problems. Also techniques like diagonalization is easier to be applied on syntactic classes, since they have a natural machine enumeration. But still $\mathsf{BPP}$ as a semantic class seems to have much more nice properties than the syntactic class $\mathsf{PP}$.

What benefits do we have if we have a syntactic representation of a semantic class, or vice versa? Are there results or proof techniques only applied to syntactic/semantic classes?

• It can never hurt to have a syntactic characterization of a semantic class. I don't see how one can compare the benefits of having a syntactic or semantic characterization of a class. BPP is not known to have a syntactic characterization, but it is widely believed to have one (if P = BPP), so the fact that BPP has "nice properties" doesn't seem to have anything to do with it being a semantic class. – Robin Kothari Feb 8 '11 at 17:55
• @Robin: Thanks for the comment. So we should consider a semantic class which is not believed to have a syntactic characterization, say the unambiguous poly-time $\mathsf{UP}$. But it doesn't have too much "nice properties" though. Any other examples? – Hsien-Chih Chang 張顯之 Feb 8 '11 at 18:05
• on the "or vice versa": what would a semantic characterization of a syntactic class be? Is there examples of a semantic class without such a semantic characterization? – Artem Kaznatcheev Feb 8 '11 at 22:00
• @Artem: I guess the class $\mathsf{NP}$ counts? A nice syntactic class it is, but no known semantic characterization exists. (Unlike the plausible conjecture $\mathsf{NL} = \mathsf{UL}$, which reduces the syntactic class $\mathsf{NL}$ into something only accepts or rejects with specific patterns; here accepts only if there is a unique accepting computation path and rejects if there is none.) – Hsien-Chih Chang 張顯之 Feb 9 '11 at 14:11

1. Syntactic classes give you time hierarchies. Zak's proof of the nondeterministic time hierarchy works for any syntactic class. For semantic classes (like UPTIME($n^3$)?$=$UTPIME($n^2$)) these are open questions.