Can the $\mathsf{P}^{\#\mathsf{P}}$ (= $\mathsf{P}^{\mathsf{PP}}$) class be described in terms of a non-deterministic Turing machine (in particular, an alternating Turing machine)? And would a $\mathsf{P}^{\#\mathsf{P}}$ machine be equivalent in computational power to any non-deterministic Turing machine? I suppose it should be because $\mathsf{P}^{\#\mathsf{P}}$ lies in between $\mathsf{PSPACE}$ and $\mathsf{PH}$ as per this, and both $\mathsf{PSPACE}$ and $\mathsf{PH}$ are describable in terms of alternating Turing machines. However, I could not find any description of $\mathsf{P}^{\#\mathsf{P}}$ or $\mathsf{P}^{\mathsf{PP}}$ in terms of alternating Turing machines, so far.

  • $\begingroup$ It is an open problem weather under SETH, there's a tight reduction from QBF-SAT TO #CNF-SAT as per this talk (~2 minutes before the ending): youtube.com/watch?v=CIsfsGGOmKI $\endgroup$
    – Avi Tal
    Commented Dec 22, 2019 at 2:32
  • $\begingroup$ @S.D. You could define "Threshold" Turing Machines using counting quantifiers instead of alternating quantifiers and they capture the Counting Hierarchy and in particular $P^{\# P}$. See for example, researchgate.net/profile/Eric_Allender/publication/… $\endgroup$
    – Nikhil
    Commented Dec 22, 2019 at 14:05


Your Answer

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