1
$\begingroup$

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?
Improve this question
$\endgroup$
8
  • $\begingroup$ @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? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Feb 5, 2011 at 16:39
  • $\begingroup$ Yes it does run in polynomial time. I do not understand the question. $\endgroup$
    – Tayfun Pay
    Feb 5, 2011 at 16:44
  • $\begingroup$ @Tayfun Pay: I mean, is it possible that this class is not in PH? $\endgroup$
    – Hsien-Chih Chang 張顯之
    Feb 5, 2011 at 16:46
  • 2
    $\begingroup$ 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. $\endgroup$
    – Hsien-Chih Chang 張顯之
    Feb 5, 2011 at 17:07
  • 4
    $\begingroup$ (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. $\endgroup$
    – Tsuyoshi Ito
    Feb 5, 2011 at 22:20

1 Answer 1

Reset to default
5
$\begingroup$

@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], (or directly to [Hertrampf et all 93]), 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!

Improve this answer
$\endgroup$
2
  • $\begingroup$ @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? $\endgroup$
    – Tayfun Pay
    Feb 5, 2011 at 20:25
  • 4
    $\begingroup$ 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? $\endgroup$
    – Tsuyoshi Ito
    Feb 5, 2011 at 20:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.