Skip to main content
deleted 4 characters in body
Source Link

Another interesting condition is this:

We know that approximating $\#3SAT$ is in $BPP^{NP}$ (Now $BPP$ in $\Sigma_2^{P}$ makes approximating $\#3SAT$ in $\Sigma_3^{P}$).

Also, By Toda's theorem, $PH \subseteq P^{\#P}$.

Combining these two, we get: If approximating $\#3SAT$ is not equivalent to computing $\#3SAT$ exactly, then Polynomial Hierarchy collapses.

Another interesting condition is this:

We know that approximating $\#3SAT$ is in $BPP^{NP}$ (Now $BPP$ in $\Sigma_2^{P}$ makes approximating $\#3SAT$ in $\Sigma_3^{P}$).

Also, By Toda's theorem, $PH \subseteq P^{\#P}$.

Combining these two, we get: If approximating $\#3SAT$ is not equivalent to computing $\#3SAT$ exactly, then Polynomial Hierarchy collapses.

Another interesting condition is this:

We know that approximating $\#3SAT$ is in $BPP^{NP}$ (Now $BPP$ in $\Sigma_2^{P}$ makes approximating $\#3SAT$ in $\Sigma_3^{P}$).

Also, By Toda's theorem, $PH \subseteq P^{\#P}$.

Combining these two, we get: If approximating $\#3SAT$ is equivalent to computing $\#3SAT$ exactly, then Polynomial Hierarchy collapses.

Source Link

Another interesting condition is this:

We know that approximating $\#3SAT$ is in $BPP^{NP}$ (Now $BPP$ in $\Sigma_2^{P}$ makes approximating $\#3SAT$ in $\Sigma_3^{P}$).

Also, By Toda's theorem, $PH \subseteq P^{\#P}$.

Combining these two, we get: If approximating $\#3SAT$ is not equivalent to computing $\#3SAT$ exactly, then Polynomial Hierarchy collapses.