Benefits for syntactic and semantic classes

Question

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?

Answer 1

Here are a couple of advantages.

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.
2. It's easier to create oracles that separate syntactic classes since you only need to diagonalize infinitely often and you don't care what happens on the other input lengths. Conversely it's easier to collapse semantic classes since you can eliminate machines that don't fulfill the promise.

Answer 2

I think, at this level of generality, you've already highlighted some of the main values of syntactic classes in the question: they have an enumeration of machines, and as a consequence they have natural complete problems and one can more easily do diagonalization. Of course, specific semantic classes (such as UP) may have other benefits, but for just "syntactic vs semantic" in general, I think the machine enumeration and its conseequences are the main benefit.

Answer 3

I believe the benefit of creating a semantic class is to be able to isolate the answers you actually wish. For example, in UP we are either concerned if there are one solutions or zero solutions and we do not care if there are more then one solutions. I believe semantic class is a way of fine-tuning syntactic classes.