<p>@Tayfun Pay, you are trying to get us to solve a problem for you!  </p>

<p>As it turns out, you only need to apply primality on the count of the number of accepting paths and this count requires polynomial number bits to write down. But the concatenated string on the paths of the NP machine is exponentially long. It is as if the primality algorithm is run on a "padded/unary" version. So it is quite weak and runs within logspace and hence the whole things is within PSPACE.</p>

<p>Now, if you refer to the table (Figure 1) in this paper by <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.7283" rel="nofollow">[Jenner et al]</a>, (or directly to <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.2093" rel="nofollow">[Hertrampf et all 93]</a>), you will notice that classes within PSPACE (ModP/PH etc) emerge only when the leaf language is a subset of regular languages such as solvable/aperiodic etc. But as is well known, unary PRIMES is not regular (by standard application of pumping lemma).</p>

<p>This much I know. Now to your question. I would suspect PSPACE is the right bound and the proof should not be too difficult, given the techniques from the papers quoted above. If you spend some time thinking, I am sure you will be able to prove the correct bound one way or the other. And especially if these are your first steps into research, I will say, go for it!</p>

CC BY-SA 2.5
2011-02-05T20:25:01.090Z
@V Vinay: Thank you for your answer! If we use a Parity-P Oracle, we can partially solve the problem? If the number of accepting paths are even, then it is composite. On the other hand, if the number of accepting paths are odd it can either be composite or even. So I assume we can solve it with an oracle in between Parity-P and PP... So it is somewhere in the polynomial hierarchy? No?
Tayfun Pay
CC BY-SA 2.5
2011-02-05T20:33:19.047Z
I thought that the class in the question is obviously contained in P^#P (=P^PP).  Why is it a problem whether it is contained in PSPACE or not?
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-05T19:53:49.530Z
2011-02-05T19:53:49.530Z
V Vinay
<p>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}. </p>

<p>Lets call the Above language CA-PR (Composite Accept - Prime Reject). </p>

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

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

<p><strong>Questions</strong>:</p>

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

CC BY-SA 2.5
2011-02-05T16:39:32.677Z
@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?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-05T16:44:55.957Z
Yes it does run in polynomial time. I do not understand the question.
Tayfun Pay
CC BY-SA 2.5
2011-02-05T16:46:47.693Z
@Tayfun Pay: I mean, is it possible that this class is not in **PH**?
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-05T17:01:32.747Z
I just edited it.
Tayfun Pay
CC BY-SA 2.5
2011-02-05T17:07:26.723Z
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.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-02-05T22:20:46.977Z
(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.
Tsuyoshi Ito
CC BY-SA 2.5
2011-02-06T03:26:37.343Z
@Tsuyoshi Ok I think I fixed it... Can you explain how coUP is contained in it? Thanks
Tayfun Pay
CC BY-SA 2.5
2011-02-06T06:17:43.113Z
Let L be a decision problem in coUP.  Then there exists a nondeterministic polynomial-time Turing machine M such that M has no accepting paths if the input is a yes-instance for L and exactly one accepting path if the input is a no-instance.  Construct M′ which has exactly four more accepting paths than M (exercise: how?).  Then M′ has exactly four (which is composite) accepting paths for yes-instances and five (which is prime) accepting paths for no-instances.
Tsuyoshi Ito
<cc.complexity-theory><counting-complexity><polynomial-hierarchy>
Complexity of a certain leaf language with Prime & Composite number of accepting paths.
Tayfun Pay
# Complexity of a certain leaf language with Prime & Composite number of accepting paths.

(Asked by: username_0 on 2011-02-05)

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?

**Tags:** cc.complexity-theory, counting-complexity, polynomial-hierarchy
> **Comments:**
> **username_1**: @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?  
> **username_0**: Yes it does run in polynomial time. I do not understand the question.  
> **username_1**: @Tayfun Pay: I mean, is it possible that this class is not in **PH**?  
> **username_0**: I just edited it.  
> **username_1**: 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.  
> **username_2**: (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.  
> **username_0**: @Tsuyoshi Ok I think I fixed it... Can you explain how coUP is contained in it? Thanks  
> **username_2**: Let L be a decision problem in coUP.  Then there exists a nondeterministic polynomial-time Turing machine M such that M has no accepting paths if the input is a yes-instance for L and exactly one accepting path if the input is a no-instance.  Construct M′ which has exactly four more accepting paths than M (exercise: how?).  Then M′ has exactly four (which is composite) accepting paths for yes-instances and five (which is prime) accepting paths for no-instances.  

---

## 1 answers

### Answer by username_3 on 2011-02-05. Score: 5 | Accepted answer

@Tayfun Pay, you are trying to get us to solve a problem for you!

As it turns out, you only need to apply primality on the count of the number of accepting paths and this count requires polynomial number bits to write down. But the concatenated string on the paths of the NP machine is exponentially long. It is as if the primality algorithm is run on a "padded/unary" version. So it is quite weak and runs within logspace and hence the whole things is within PSPACE.

Now, if you refer to the table (Figure 1) in this paper by [[Jenner et al]](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.51.7283), (or directly to [[Hertrampf et all 93]](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.54.2093)), you will notice that classes within PSPACE (ModP/PH etc) emerge only when the leaf language is a subset of regular languages such as solvable/aperiodic etc. But as is well known, unary PRIMES is not regular (by standard application of pumping lemma).

This much I know. Now to your question. I would suspect PSPACE is the right bound and the proof should not be too difficult, given the techniques from the papers quoted above. If you spend some time thinking, I am sure you will be able to prove the correct bound one way or the other. And especially if these are your first steps into research, I will say, go for it!

> **Comments:**
> **username_0**: @V Vinay: Thank you for your answer! If we use a Parity-P Oracle, we can partially solve the problem? If the number of accepting paths are even, then it is composite. On the other hand, if the number of accepting paths are odd it can either be composite or even. So I assume we can solve it with an oracle in between Parity-P and PP... So it is somewhere in the polynomial hierarchy? No?  
> **username_2**: I thought that the class in the question is obviously contained in P^#P (=P^PP).  Why is it a problem whether it is contained in PSPACE or not?  

---

