<p>Can the <span class="math-container">$\mathsf{P}^{\#\mathsf{P}}$</span> (= <span class="math-container">$\mathsf{P}^{\mathsf{PP}}$</span>) class be described in terms of a non-deterministic Turing machine (in particular, an alternating Turing machine)? And would a <span class="math-container">$\mathsf{P}^{\#\mathsf{P}}$</span> machine be equivalent in computational power to any non-deterministic Turing machine? I suppose it should be because <span class="math-container">$\mathsf{P}^{\#\mathsf{P}}$</span> lies in between <span class="math-container">$\mathsf{PSPACE}$</span> and <span class="math-container">$\mathsf{PH}$</span> as per <a href="https://complexityzoo.uwaterloo.ca/File:Really-important-inclusions.png" rel="nofollow noreferrer">this</a>, and both <span class="math-container">$\mathsf{PSPACE}$</span> and <span class="math-container">$\mathsf{PH}$</span> are describable in terms of alternating Turing machines. However, I could not find any description of <span class="math-container">$\mathsf{P}^{\#\mathsf{P}}$</span> or <span class="math-container">$\mathsf{P}^{\mathsf{PP}}$</span> in terms of alternating Turing machines, so far. </p>

CC BY-SA 4.0
2019-12-22T02:32:47.927Z
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): https://www.youtube.com/watch?v=CIsfsGGOmKI
Avi Tal
CC BY-SA 4.0
2019-12-22T14:05:32.797Z
@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, https://www.researchgate.net/profile/Eric_Allender/publication/2748367_Counting_Hierarchies_Polynomial_Time_And_Constant_Depth_Circuits/links/09e41513dfb20a76e4000000.pdf
Nikhil
<cc.complexity-theory><turing-machines>
Can $\mathsf{P}^{\#\mathsf{P}}$ be described in terms of a non-deterministic (alternating) Turing machine?
Sanchayan Dutta
# Can $\mathsf{P}^{\#\mathsf{P}}$ be described in terms of a non-deterministic (alternating) Turing machine?

(Asked by: username_0 on 2019-12-21)

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](https://complexityzoo.uwaterloo.ca/File:Really-important-inclusions.png), 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.

**Tags:** cc.complexity-theory, turing-machines

> **Comments:**
> **username_1**: 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): https://www.youtube.com/watch?v=CIsfsGGOmKI  
> **username_2**: @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, https://www.researchgate.net/profile/Eric_Allender/publication/2748367_Counting_Hierarchies_Polynomial_Time_And_Constant_Depth_Circuits/links/09e41513dfb20a76e4000000.pdf  

---

## 0 answers

