- cc.complexity-theory counting-complexity
- Updated Thu, 09 Jun 2022 00:37:47 GMT

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

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.

External links referenced by this document: