#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?
$\begingroup$
$\endgroup$
9
-
9$\begingroup$ I doubt anyone has defined such a class, but I don't see a reason why you couldn't. $\endgroup$– user1338Commented Feb 2, 2011 at 21:57
-
8$\begingroup$ You just defined it, therefore it exists. Rule 34 in TCS. $\endgroup$– RaphaelCommented Feb 2, 2011 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 ItoCommented Feb 2, 2011 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 TaylorCommented Feb 2, 2011 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 ItoCommented Feb 2, 2011 at 23:39
|
Show 4 more comments
3 Answers
$\begingroup$
$\endgroup$
2
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$ Commented Feb 5, 2011 at 16:29
-
$\begingroup$ I did ask a another question relating to this. $\endgroup$ Commented Feb 5, 2011 at 16:29
$\begingroup$
$\endgroup$
4
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.
answered Feb 2, 2011 at 23:55
-
$\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$ Commented Feb 3, 2011 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$ Commented Feb 3, 2011 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$ Commented Feb 3, 2011 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$ Commented Feb 3, 2011 at 2:08
$\begingroup$
$\endgroup$
Mod$_k$P is a generalisation of Mod$_2$P = $\oplus$P.
answered Feb 2, 2011 at 23:53