# Complexity of a certain leaf language with Prime & Composite number of accepting paths.

Given a non-deterministic Turing Machine that runs in polynomial time, it accepts if the number of accepting paths are composite, it rejects if the number of accepting paths are prime and it outputs I do not know if the number of accepting paths are {0,1}.

Lets call the Above language CA-PR (Composite Accept - Prime Reject).

Then we have co-CA-PR = PA-CR(Prime accept, composite reject).

Both of the above languages output DON'T KNOW when the number of accepting paths are {0,1}.

Questions:

1. Do CA-PR & PA-CR not contain UP?
2. A #P Oracle can definitely solve these problems, can a PP oracle too? How about a ParityOracle?
3. What can we say about the intersection and union of these languages?
4. Where can we place this complexity class? Is it in the polynomial hierarchy?
• @Geekster: Does the machine run in polynomial time? Even so, I'm not sure if this class would be in PH. (I only have a rough upper bound EXP.) Would you like to explain why this is the case? Feb 5, 2011 at 16:39
• Yes it does run in polynomial time. I do not understand the question. Feb 5, 2011 at 16:44
• @Tayfun Pay: I mean, is it possible that this class is not in PH? Feb 5, 2011 at 16:46
• Hum. I guess the class can be shown in $\mathsf{PSPACE}$. We just simulate the non-deterministic moves, and count the number of accepting paths; finally we apply primality test on the number of accepting paths. All of these can be done in polynomial space. Feb 5, 2011 at 17:07
• (1) Easy facts: CAPR is contained in P^#P (=P^PP), and contains both NP and coUP. (Proving P^#P=P^PP is a standard exercise.) (2) You appear to be confusing languages and classes in several places in the question. Feb 5, 2011 at 22:20