Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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

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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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