Semantic vs. Syntactic Complexity Classes

Question

In his "Computational Complexity" book, Papadimitriou writes:

RP is in some sense a new and unusual kind of complexity class. Not any polynomially bounded nondeterministic Turing machine can be the basis of defining a language in RP. For a machine N to define a language in RP, it must have the remarkable property that on all inputs it either rejects unanimously, or it accepts by majority. Most nondeterministic machines behave in other ways for at least some inputs ... There is no easy way to tell whether a machine always halts with a certified output. We informally call such classes semantic classes, as opposed to the syntactic classes such as P and NP, where we can tell immediately by a superficial check whether an appropriately standardized machine indeed defines a language in the class.

Several pages later, he points that:

language L is in the class PP if there is a nondeterministic polynomially bounded Turing machine N such that, for all inputs x, $x \in L$ iff more than half of the computations of N on input x end up accepting. We say that N decides L by majority.

Question 1: Why Papadimitriou concludes that PP is a syntactic class, while its definition is only slightly different from that of RP?

Question 2: Whether being "semantic" for a complexity class is equivalent to NOT having complete problems, or the lack of complete problems is thought of as a property that we GUESS semantic classes possess?

Edit: See related topic Do all complexity classes have a leaf language characterization?

Answer 1

RP involves a promise, that either 0 paths accept or more than half accept, no matter what the input is. For PP, there is no such promise. If more than half the paths accept, then $x \in L$, otherwise, $x \notin L$. (PP can be defined so that the acceptance criteria are $\geq 1/2$ and $< 1/2$ respectively.)

Or in other words, if I give you a probabilistic TM claiming it is a PP machine deciding some language, you can be sure that it decides some language. Clearly, the language it decides is this one: Try input $x$. See if more than 1/2 of the paths accept (or more than 1/2 random strings cause it to accept). If so, $x \in L$. If not, $x \notin L$. So we've defined a language using this TM.

On the other hand, if I give you a probabilistic TM claiming it is a RP machine deciding some language, you can't even be sure that it decides any language. The problem is that when you observe only a few paths accepting, you don't know if $x$ is in $L$ or not. So if I give you a RP machine, you just have to take my word for it. Indeed, checking if this machine defines a language is uncomputable.

As for your second question, for syntactic classes usually there's an obvious complete problem, which is like "Given machine M, decide if it accepts in time T on input x." If you're given a nondeterministic machine, this problem is NP-complete, if it's a PP-machine, then it's PP-complete, etc. The obvious complete problem for semantic classes is undecidable, as I mentioned. So we don't get a complete problem for free for semantic classes. But a semantic class can have a complete problem. For example if P = BPP (as is widely believed), then BPP has a syntactic characterization.

EDIT: Since there's some discussion on how to define semantic and syntactic classes, I'd like to point out that Papadimitriou gives a definition in his book when talking about leaf languages. (See my question about leaf languages for some references.)

He says that syntactic classes are those for which there exists some language that defines the class using the leaf language technique. Semantic classes are those for which all such characterizations require promise problems. This is a rigorous definition, but only works for those languages that have leaf language characterizations.

Answer 2

The answer to your first question is that in the definition of $PP$, there is no "promise" for a machine to satisfy, like with $RP$. Every randomized polytime machine defines some $PP$ language: on each input, either the machine accepts on $> 1/2$ of the random computation paths on the appropriate inputs, or it doesn't. The first case means $x$ is in the language, the second case means it's not in.

Hence, just like in the case of $P$ and $NP$, we can give a recursive list of all $PP$-machines, by simply listing all randomized polytime machines. In contrast, with $RP$, there are randomized machines which accept (for example) exactly one of the random strings on an input, in which case the machine does not satisfy either condition for $RP$: it does not accept on $> 1/2$ of its random strings, and it does not reject all strings. Hence this randomized machine is not an $RP$-machine, in the sense that it has "undefined" behavior on some subset of inputs. This leads to the definition of $Promise-RP$, where you consider "promise problems" which permit arbitrary behavior on some strings. See the Complexity Zoo for more.

This leads to question 2. The problem with the notion of a "semantic class" is that it depends on the machines you're using to define the class, and hence it is extremely subtle to properly define. (I am not sure that a completely satisfactory definition has ever been given.) Being a "semantic class" is roughly equivalent to the property stated above: not every machine (in a natural listing of machines) will satisfy the acceptance/rejection conditions needed for your class, and hence it's "hard" to get a list of machines that accept exactly the languages in your class. But if $P=BPP$, then there is some easily computable list of some machines that accept exactly the languages in your class: namely, the list of polynomial time computable machines. Hence it would appear that, if it turns out that $P=BPP$, we have turned a semantic class into a syntactic one.

If it were truly the case that there is simply no easily computable list of machines (of any reasonable kind) that accept exactly your class, then yes, I do not think your class can possibly have a complete language. But that seems very hard to formalize properly, let alone prove.