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$
$\endgroup$
2
-
$\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 TalDec 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$– NikhilDec 22, 2019 at 14:05
Add a comment
|