<p>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 <em>some</em> $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.</p>

<p>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 <em>not</em> 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.</p>

<p>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 <em>some</em> easily computable list of <em>some</em> 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. </p>

<p>If it were truly the case that there is simply <em>no</em> 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.</p>

CC BY-SA 2.5
2010-09-13T05:43:54.767Z
Hi Ryan. Do you think it is possible to define syntactic-ness by assuming something like Church-Turing Thesis?
Kaveh
CC BY-SA 2.5
2010-09-13T06:15:29.667Z
I've edited my answer now to address the question of how to _define_ syntacticness.
Robin Kothari
CC BY-SA 2.5
2010-09-13T04:14:52.540Z
2010-09-13T04:14:52.540Z
Ryan Williams
<p>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 $&lt; 1/2$ respectively.)</p>

<p>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 <em>some</em> 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.</p>

<p>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.</p>

<p>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.</p>

<p><strong>EDIT</strong>: Since there's some discussion on how to <em>define</em> semantic and syntactic classes, I'd like to point out that Papadimitriou gives a definition in his book when talking about leaf languages. (See <a href="https://cstheory.stackexchange.com/q/761/206">my question about leaf languages</a> for some references.)</p>

<p>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.</p>

CC BY-SA 2.5
2010-09-13T04:17:03.510Z
Well, I would not have wasted the last 20 minutes writing my answer, if I had just reloaded the page... :) I'll leave it just in case it is also helpful.
Ryan Williams
CC BY-SA 2.5
2010-09-13T06:16:38.817Z
Yeah, I hate it when that happens. Although sometimes I get the "new answers have been posted" notification in the middle of composing an answer.
Robin Kothari
CC BY-SA 2.5
2010-09-14T16:52:17.627Z
@Robin: You didn't have to resort to the unproven but widely believed assertion "P=BPP" for an example of an intensionally semantic class that turns out to be syntactic: IP = PSPACE. (And now QIP too.)
Joshua Grochow
CC BY-SA 2.5
2010-09-14T18:18:18.060Z
@Joshua: You're right, IP = PSPACE works.
Robin Kothari
CC BY-SA 2.5
2010-09-22T02:48:31.347Z
@Joshua: Thanks for mentioning the IP = PSPACE result. I've never looked at it from this viewpoint!
Sadeq Dousti
CC BY-SA 2.5
2010-09-13T03:54:30.490Z
2010-09-13T06:14:31.520Z
2017-04-13T12:32:28.053Z
Robin Kothari
<p>In his "Computational Complexity" book, Papadimitriou writes:</p>

<blockquote>
  <p><strong>RP</strong> 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 <em>N</em> to define a language in <strong>RP</strong>, it must have the remarkable property that on all inputs it either rejects <em>unanimously</em>, or it accepts <em>by majority</em>. 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 <strong>semantic classes</strong>, as opposed to the <strong>syntactic classes</strong> such as <strong>P</strong> and <strong>NP</strong>, where we can tell immediately by a superficial check whether an appropriately standardized machine indeed defines a language in the class.</p>
</blockquote>

<p>Several pages later, he points that:</p>

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

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

<p><strong>Question 2:</strong> 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?</p>

<p><strong>Edit:</strong> See related topic <a href="https://cstheory.stackexchange.com/q/761/873">Do all complexity classes have a leaf language characterization?</a></p>

CC BY-SA 3.0
2012-04-23T05:56:04.390Z
a related recent talk by Anuj Davar at INI: [On syntactic and semantic complexity classes](http://www.newton.ac.uk/programmes/SAS/seminars/010916301.html)
Kaveh
CC BY-SA 3.0
2012-04-23T10:34:14.277Z
@Kaveh: Thanks a lot! I'll take a look at it.
Sadeq Dousti
<cc.complexity-theory><complexity-classes><big-picture>
Semantic vs. Syntactic Complexity Classes
Sadeq Dousti
# Semantic vs. Syntactic Complexity Classes

(Asked by: username_0 on 2010-09-13)

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?](https://cstheory.stackexchange.com/q/761/873)

**Tags:** cc.complexity-theory, complexity-classes, big-picture

> **Comments:**
> **username_1**: a related recent talk by Anuj Davar at INI: [On syntactic and semantic complexity classes](http://www.newton.ac.uk/programmes/SAS/seminars/010916301.html)  
> **username_0**: @username_1: Thanks a lot! I'll take a look at it.  

---

## 2 answers

### Answer by username_3 on 2010-09-13. Score: 36 | Accepted answer

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](https://cstheory.stackexchange.com/q/761/206) 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.

> **Comments:**
> **username_2**: Well, I would not have wasted the last 20 minutes writing my answer, if I had just reloaded the page... :) I'll leave it just in case it is also helpful.  
> **username_3**: Yeah, I hate it when that happens. Although sometimes I get the "new answers have been posted" notification in the middle of composing an answer.  
> **username_4**: @Robin: You didn't have to resort to the unproven but widely believed assertion "P=BPP" for an example of an intensionally semantic class that turns out to be syntactic: IP = PSPACE. (And now QIP too.)  
> **username_3**: @Joshua: You're right, IP = PSPACE works.  
> **username_0**: @Joshua: Thanks for mentioning the IP = PSPACE result. I've never looked at it from this viewpoint!  

---

### Answer by username_2 on 2010-09-13. Score: 31

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.

> **Comments:**
> **username_1**: Hi Ryan. Do you think it is possible to define syntactic-ness by assuming something like Church-Turing Thesis?  
> **username_3**: I've edited my answer now to address the question of how to _define_ syntacticness.  

---

