Theoretical Computer Science
cc.complexity-theory counting-complexity polynomial-hierarchy
Updated Wed, 22 Jun 2022 05:13:36 GMT

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?

Solution

@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!

Comments (2)

  • +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? — Feb 05, 2011 at 20:25  
  • +4 – 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? — Feb 05, 2011 at 20:33  

External Links

External links referenced by this document:

References