#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?

  • 9
    $\begingroup$ I doubt anyone has defined such a class, but I don't see a reason why you couldn't. $\endgroup$ – Philip White Feb 2 '11 at 21:57
  • 8
    $\begingroup$ You just defined it, therefore it exists. Rule 34 in TCS. $\endgroup$ – Raphael Feb 2 '11 at 22:58
  • 10
    $\begingroup$ @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, we cannot call it coCP, either (even if we ignore the issue that 0 and 1 are neither prime nor composite). Stuck! $\endgroup$ – Tsuyoshi Ito Feb 2 '11 at 23:01
  • 3
    $\begingroup$ @Geekster, how did you get on to reals? You were talking about a subset of the integers just a moment ago... $\endgroup$ – Peter Taylor Feb 2 '11 at 23:25
  • 4
    $\begingroup$ @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! $\endgroup$ – Tsuyoshi Ito Feb 2 '11 at 23:39

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]. More on this here as well. You may also find this survey on leaf languages helpful.

  • $\begingroup$ This survey is it! Very nice! Thank you so much! $\endgroup$ – Tayfun Pay Feb 5 '11 at 16:29
  • $\begingroup$ I did ask a another question relating to this. $\endgroup$ – Tayfun Pay Feb 5 '11 at 16:29

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, AWPP, C=P, Few, FewP, LWPP, ModkP, SPP and 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 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.

  • $\begingroup$ 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. $\endgroup$ – Tayfun Pay Feb 3 '11 at 1:24
  • $\begingroup$ 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? $\endgroup$ – Tayfun Pay Feb 3 '11 at 1:45
  • $\begingroup$ @Geekster: I do not know of any book like that. I have seen that The Complexity Theory 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) $\endgroup$ – Tsuyoshi Ito Feb 3 '11 at 2:01
  • 3
    $\begingroup$ (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! $\endgroup$ – Tsuyoshi Ito Feb 3 '11 at 2:08

Mod$_k$P is a generalisation of Mod$_2$P = $\oplus$P.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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