Does there exist a complexity class such that 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.

Solved by user1449 (3,813 )
Feb 05, 2011 at 05:40