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 Dec 22 '19 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 Dec 22 '19 at 14:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.