<p>Many other complexity classes which have appeared in literature are defined in terms of the number of accepting paths.  Just for fun, examples from the Complexity Zoo include <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aG#gapp" rel="nofollow">GapP</a>, <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aA#awpp" rel="nofollow">AWPP</a>, <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#cequalsp" rel="nofollow">C<sub>=</sub>P</a>, <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aF#few" rel="nofollow">Few</a>, <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aF#fewp" rel="nofollow">FewP</a>, <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aL#lwpp" rel="nofollow">LWPP</a>, <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aM#modkp" rel="nofollow">Mod<sub><i>k</i></sub>P</a>, <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#spp" rel="nofollow">SPP</a> and <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aW#wpp" rel="nofollow">WPP</a>.  Also do not forget the logarithmic-space versions of these classes.</p>

<p>A serious fact is that the definition of randomized complexity classes such as the very important <a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aB#bpp" rel="nofollow">BPP</a> can be viewed as based on the number of accepting paths.</p>

<p>As for the class of decision problems which have a nondeterministic polynomial-time Turing machine such that yes-instances have a prime number of accepting paths and no-instances have a composite number of accepting paths: As Philip White and other people wrote in comments on the question, you could define it.  Whether that class has any interesting property or not is a separate issue.</p>

CC BY-SA 2.5
2011-02-03T01:24:39.667Z
Thank you for your serious reply. I am trying to come up with a thesis topic. I want to do something along the lines of #P, counting classes, & Phase Transition. However, I do not have a definite topic yet. I have came up with certain counting functions for SAT but I do not know where it would fit... Once again, thank you for your reply. I will ponder about why it could be important.
Tayfun Pay
CC BY-SA 2.5
2011-02-03T01:45:17.307Z
Is there such a book that defines and discusses most if not all of the Complexity Classes that are mentioned in the Complexity Zoo? And why they are important?
Tayfun Pay
CC BY-SA 2.5
2011-02-03T02:01:11.407Z
@Geekster: I do not know of any book like that.  I have seen that [The Complexity Theory Companion](http://www.cs.rochester.edu/~lane/=companion/) contains a list of a lot of complexity classes, but I do not have a copy with me and I do not remember how much they focus on the motivation.  (more)
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-03T02:08:27.043Z
(cont’d)  Just to make sure, most of the classes I mentioned in the answer are important only in certain context and in some specific sense (and I cannot explain most of them).  I do not know whether you are aiming at graduate thesis, master thesis or PhD thesis, but I hope that this answer will not mislead you that proving a random result about an obscure class will be a good research.  I wish you will find a good topic!
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-02T23:55:03.513Z
2011-02-03T00:00:36.940Z
2011-02-03T00:00:36.940Z
Tsuyoshi Ito
<p><a href="http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aM#modkp" rel="nofollow">Mod$_k$P</a> is a generalisation of Mod$_2$P = $\oplus$P.</p>

CC BY-SA 3.0
2011-02-02T23:53:39.690Z
2011-08-31T16:56:41.377Z
2011-08-31T16:56:41.377Z
Jukka Suomela
<p>What you are looking for is likely Leaf Languages. Look at the output of each path of an NP machine and concatenate them into an exponentially long string. We can now talk of the machine accepting the input if the leaf string belongs to a fixed language; the leaf language. (Well, there are usually two languages; one for accepting and the other for rejection. There are many variations to the basic defn too.)</p>

<p>So you could ask, what happens if my leaf language is a regular language or context-free etc. All this has been studied extensively in the 1990's and even lead to the uniform separation of $TC^0$ from the counting hierarchy due to Caussinus, McKenzie, Therien, Vollmer <a href="http://www.iro.umontreal.ca/~mckenzie/camcthvo97.ps" rel="nofollow">[CMTV98]</a>. More on this <a href="http://cjtcs.cs.uchicago.edu/articles/1999/7/contents.html" rel="nofollow">here as well</a>. You may also find this <a href="http://haegar.informatik.uni-wuerzburg.de/TRs/tr372.ps" rel="nofollow">survey</a> on leaf languages helpful.</p>

CC BY-SA 2.5
2011-02-05T16:29:29.617Z
This survey is it! Very nice! Thank you so much!
Tayfun Pay
CC BY-SA 2.5
2011-02-05T16:29:53.907Z
I did ask a another question relating to this.
Tayfun Pay
CC BY-SA 2.5
2011-02-05T05:40:57.647Z
2011-02-05T05:40:57.647Z
V Vinay
<p>#P asks the total number of accepting paths.<br> 
PP asks at least half of paths be accepting. <br>
Parity-P asks the number of accepting paths be even.<br> 
UP asks the number of accepting paths to be one. <br>
Are there any other Complexity Classes like this? For example, does there exist a complexity class where the number of accepting paths is a prime number?</p>

CC BY-SA 2.5
2011-02-02T22:58:47.393Z
You just defined it, therefore it exists. Rule 34 in TCS.
Raphael
CC BY-SA 2.5
2011-02-02T23:01:24.657Z
@Philip: It cannot be defined because it would be obviously named PP for prime polynomial-time but the name PP is already taken.  Moreover, since CP (where C stands for composite) is [also already taken](http://qwiki.stanford.edu/index.php/Complexity_Zoo:C#cp), we cannot call it coCP, either (even if we ignore the issue that 0 and 1 are neither prime nor composite).  Stuck!
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-02T23:18:47.860Z
@Tsuhoshi Ito.. Thanks for the clarification! :)
Tayfun Pay
CC BY-SA 2.5
2011-02-02T23:20:14.893Z
@Raphael.. Why would it be important? That's the real real question! :)
Tayfun Pay
CC BY-SA 2.5
2011-02-02T23:25:12.060Z
@Geekster, how did you get on to reals? You were talking about a subset of the integers just a moment ago...
Peter Taylor
CC BY-SA 2.5
2011-02-02T23:39:08.277Z
@Peter: Your comment is tempting me to vote to close this question as “not a real question.”  But I realized that most questions on this site are not real questions in that sense.  Oh, no, I only have 12 votes to close per day!
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-03T09:26:41.820Z
Guys, seriously...
Raphael
CC BY-SA 2.5
2011-02-04T23:05:30.003Z
@Geekster, Tsuyoshi had fixed a number of mistakes in your post, why did you roll back to the previous version?
Kaveh
<cc.complexity-theory><counting-complexity>
Does there exist a complexity class such that the number of accepting paths is a prime number?
Tayfun Pay
# Does there exist a complexity class such that the number of accepting paths is a prime number?

(Asked by: username_0 on 2011-02-02)

#P asks the total number of accepting paths.  
PP asks at least half of paths be accepting.   
Parity-P asks the number of accepting paths be even.  
UP asks the number of accepting paths to be one.   
Are there any other Complexity Classes like this? For example, does there exist a complexity class where the number of accepting paths is a prime number?

**Tags:** cc.complexity-theory, counting-complexity
> **Comments:**
> **username_1**: You just defined it, therefore it exists. Rule 34 in TCS.  
> **username_2**: @Philip: It cannot be defined because it would be obviously named PP for prime polynomial-time but the name PP is already taken.  Moreover, since CP (where C stands for composite) is [also already taken](http://qwiki.stanford.edu/index.php/Complexity_Zoo:C#cp), we cannot call it coCP, either (even if we ignore the issue that 0 and 1 are neither prime nor composite).  Stuck!  
> **username_0**: @Tsuhoshi Ito.. Thanks for the clarification! :)  
> **username_0**: @Raphael.. Why would it be important? That's the real real question! :)  
> **username_3**: @Geekster, how did you get on to reals? You were talking about a subset of the integers just a moment ago...  
> **username_2**: @Peter: Your comment is tempting me to vote to close this question as “not a real question.”  But I realized that most questions on this site are not real questions in that sense.  Oh, no, I only have 12 votes to close per day!  
> **username_1**: Guys, seriously...  
> **username_4**: @Geekster, Tsuyoshi had fixed a number of mistakes in your post, why did you roll back to the previous version?  

---

## 3 answers

### Answer by username_6 on 2011-02-05. Score: 10 | Accepted answer

What you are looking for is likely Leaf Languages. Look at the output of each path of an NP machine and concatenate them into an exponentially long string. We can now talk of the machine accepting the input if the leaf string belongs to a fixed language; the leaf language. (Well, there are usually two languages; one for accepting and the other for rejection. There are many variations to the basic defn too.)

So you could ask, what happens if my leaf language is a regular language or context-free etc. All this has been studied extensively in the 1990's and even lead to the uniform separation of $TC^0$ from the counting hierarchy due to Caussinus, McKenzie, Therien, Vollmer [[CMTV98]](http://www.iro.umontreal.ca/~mckenzie/camcthvo97.ps). More on this [here as well](http://cjtcs.cs.uchicago.edu/articles/1999/7/contents.html). You may also find this [survey](http://haegar.informatik.uni-wuerzburg.de/TRs/tr372.ps) on leaf languages helpful.

> **Comments:**
> **username_0**: This survey is it! Very nice! Thank you so much!  
> **username_0**: I did ask a another question relating to this.  

---

### Answer by username_2 on 2011-02-02. Score: 12

Many other complexity classes which have appeared in literature are defined in terms of the number of accepting paths. Just for fun, examples from the Complexity Zoo include [GapP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aG#gapp), [AWPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aA#awpp), [C=P](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aC#cequalsp), [Few](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aF#few), [FewP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aF#fewp), [LWPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aL#lwpp), [Mod*k*P](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aM#modkp), [SPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aS#spp) and [WPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aW#wpp). Also do not forget the logarithmic-space versions of these classes.

A serious fact is that the definition of randomized complexity classes such as the very important [BPP](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aB#bpp) can be viewed as based on the number of accepting paths.

As for the class of decision problems which have a nondeterministic polynomial-time Turing machine such that yes-instances have a prime number of accepting paths and no-instances have a composite number of accepting paths: As Philip White and other people wrote in comments on the question, you could define it. Whether that class has any interesting property or not is a separate issue.

> **Comments:**
> **username_0**: Thank you for your serious reply. I am trying to come up with a thesis topic. I want to do something along the lines of #P, counting classes, & Phase Transition. However, I do not have a definite topic yet. I have came up with certain counting functions for SAT but I do not know where it would fit... Once again, thank you for your reply. I will ponder about why it could be important.  
> **username_0**: Is there such a book that defines and discusses most if not all of the Complexity Classes that are mentioned in the Complexity Zoo? And why they are important?  
> **username_2**: @Geekster: I do not know of any book like that.  I have seen that [The Complexity Theory Companion](http://www.cs.rochester.edu/~lane/=companion/) contains a list of a lot of complexity classes, but I do not have a copy with me and I do not remember how much they focus on the motivation.  (more)  
> **username_2**: (cont’d)  Just to make sure, most of the classes I mentioned in the answer are important only in certain context and in some specific sense (and I cannot explain most of them).  I do not know whether you are aiming at graduate thesis, master thesis or PhD thesis, but I hope that this answer will not mislead you that proving a random result about an obscure class will be a good research.  I wish you will find a good topic!  

---

### Answer by username_5 on 2011-02-02. Score: 7

[Mod$\_k$P](http://qwiki.stanford.edu/index.php/Complexity_Zoo%3aM#modkp) is a generalisation of Mod$\_2$P = $\oplus$P.


---

