<p>This is very unlikely to hold, but (as usual) impossible to rule out using current techniques, as we can’t even prove $\mathit{PSPACE}\ne P$.</p>

<p>However, we can at least show that no <em>relativizing</em> argument proves such an inclusion, i.e., there are oracles $X$ such that randomized polynomial-time with a $(\Sigma^P_{(\log n)^c})^X$ oracle does not include $\#P^X$. Better yet, there are oracles where it does not even include $\oplus P^X$ (which is included in $P^{\#P^X}$): otherwise, there would exist $O((\log\log n)^c)$-depth quasipolynomial-size unbounded fan-in circuits that approximate parity with error, say, $1/4$, contradicting Håstad’s theorem.</p>

CC BY-SA 3.0
2017-07-19T14:25:16.593Z
2017-07-19T14:25:16.593Z
Emil Jeřábek
<ol>
<li><p>Is it known that permanent of a $0/1$ $n\times n$ matrix $M$ is computable in polynomial or randomized polynomial time with access to a ${\Sigma_{(\log n)^c}^P}$ oracle where $0&lt;c$ holds and $\Sigma_{f(n)}^P$ means the number of alternations is $f(n)$?</p></li>
<li><p>If not known what is the consequence if it is possible to do so?</p></li>
</ol>

<cc.complexity-theory><complexity-classes><permanent>
On $\#P\subseteq FP^{\Sigma_{f(n)}^P}$?
Turbo
# On $\#P\subseteq FP^{\Sigma_{f(n)}^P}$?

(Asked by: username_0 on 2017-07-11)

1. Is it known that permanent of a $0/1$ $n\times n$ matrix $M$ is computable in polynomial or randomized polynomial time with access to a ${\Sigma\_{(\log n)^c}^P}$ oracle where $0
2. If not known what is the consequence if it is possible to do so?

**Tags:** cc.complexity-theory, complexity-classes, permanent


---

## 1 answers

### Answer by username_1 on 2017-07-19. Score: 2

This is very unlikely to hold, but (as usual) impossible to rule out using current techniques, as we can’t even prove $\mathit{PSPACE}\ne P$.

However, we can at least show that no *relativizing* argument proves such an inclusion, i.e., there are oracles $X$ such that randomized polynomial-time with a $(\Sigma^P\_{(\log n)^c})^X$ oracle does not include $\#P^X$. Better yet, there are oracles where it does not even include $\oplus P^X$ (which is included in $P^{\#P^X}$): otherwise, there would exist $O((\log\log n)^c)$-depth quasipolynomial-size unbounded fan-in circuits that approximate parity with error, say, $1/4$, contradicting Håstad’s theorem.


---

