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:
- Do CA-PR & PA-CR not contain UP?
- A #P Oracle can definitely solve these problems, can a PP oracle too? How about a ParityOracle?
- What can we say about the intersection and union of these languages?
- Where can we place this complexity class? Is it in the polynomial hierarchy?