<p>In <a href="http://en.wikipedia.org/wiki/Graphical_model">graphical models</a>, many of the estimation problems are #P-complete, because they involve doing sum-product calculations a la the permanent over general graphs. If #P = FP, then graphical models suddenly get a whole lot easier, and we don't have to muck around with low-treewidth models anymore. </p>

CC BY-SA 2.5
2010-10-08T07:51:51.743Z
2010-10-08T07:51:51.743Z
Suresh Venkat
<p>Toda proved that any problem in the polynomial-time hierarchy can be reduced to #P function. Formally, he proved that $PH \subseteq P^{\#P}$. So if $\sharp P=FP$ then the $PH$ would collapse and consequently Tautologies would have short proofs.</p>

CC BY-SA 2.5
2010-10-08T07:49:52.037Z
i think it's a typo for polynomial.
Suresh Venkat
CC BY-SA 2.5
2010-10-08T07:53:47.203Z
Can someone clarify: is this not the same as saying "P=PH" (which would immediately follow from P=NP)?
Niel de Beaudrap
CC BY-SA 2.5
2010-10-08T08:12:29.590Z
@Niel: It's not the same, it is stronger.
Giorgio Camerani
CC BY-SA 2.5
2010-10-08T08:21:23.893Z
@Walter: in what way? Is not $\text P^{\text{FP}} = \text P$? If so, then $\#\text P = \text{FP}$ would imply $\text{PH} \subseteq \text P^{\#\text P} = \text P^{\text{FP}} = \text P \subseteq \text{PH}$.
Niel de Beaudrap
CC BY-SA 2.5
2010-10-08T10:24:21.267Z
@Niel: Sorry, I read your first comment too quickly and I completely misunderstood your question. Of course what you said is right. What I meant in my comment was the very obvious fact that #P = FP is a stronger statement than P = NP.
Giorgio Camerani
CC BY-SA 2.5
2010-10-08T13:07:35.010Z
@All: just to clarify --- my first comment above was asking the following question *"Is turkistany's answer equivalent to the statement that FP=#P implies P=PH?"* If I wanted to know whether FP=#P was equivalent to P=PH, I would have asked this in a comment on the original post, not on turkistany's answer.
Niel de Beaudrap
CC BY-SA 2.5
2010-10-08T13:24:10.750Z
@Niel: You're right. This is the same as saying P = PH, which follows from P = NP. Therefore the use of Toda's theorem was not necessary, since FP = #P already implies P = NP = PH.
Robin Kothari
CC BY-SA 2.5
2010-10-08T07:44:42.843Z
2010-10-08T08:27:33.797Z
2010-10-08T08:27:33.797Z
Mohammad Al-Turkistany
<p>Here are a few theoretical consequences of the equality FP=#P, although they have nothing to do with artificial intelligence.  The assumption FP=#P is equivalent to P=<a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pp" rel="nofollow noreferrer">PP</a>, so let me use the latter notation.</p>

<p>If P=PP, then we have P=<a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo:B#bqp" rel="nofollow noreferrer">BQP</a>: quantum polynomial-time computation can be simulated by classical, deterministic polynomial-time computation.  This is a direct consequence of BQP⊆PP [ADH97, FR98] (and of an earlier result BQP⊆P<sup>PP</sup> [BV97]).  On top of my knowledge, P=BQP is not known to follow from the assumption P=NP.  This situation is different from the case of randomized computation (<a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo:B#bpp" rel="nofollow noreferrer">BPP</a>): since BPP⊆NP<sup>NP</sup> [Lau83], the equality P=BPP follows from P=NP.</p>

<p>Another consequence of P=PP is that the Blum-Shub-Smale model of computation over the reals with rational constants is equvalent to Turing machines in a certain sense.  More precisely, P=PP implies P=BP(P<sub>ℝ</sub><sup>0</sup>); that is, if a language <i>L</i>⊆{0,1}<sup>*</sup> is decidable by a constant-free program over the reals in polynomial time, then <i>L</i> is decidable by a polynomial-time Turing machine.  (Here “BP” stands for “Boolean part” and has nothing to do with BPP.)  This follows from BP(P<sub>ℝ</sub><sup>0</sup>)⊆<a href="http://qwiki.stanford.edu/wiki/Complexity_Zoo:C#ch" rel="nofollow noreferrer">CH</a> [ABKM09].  See the paper for definitions.  An important problem in BP(P<sub>ℝ</sub><sup>0</sup>) is the <a href="http://garden.irmacs.sfu.ca/?q=op/complexity_of_square_root_sum" rel="nofollow noreferrer">square-root sum problem</a> and friends (e.g. “Given an integer <i>k</i> and a finite set of integer-coordinate points on the plane, is there a spanning tree of total length at most <i>k</i>?”) [Tiw92].</p>

<p>Similarly to the second argument, the problem of <a href="https://cstheory.stackexchange.com/questions/1811/complexity-of-exponential-function">computing a specific bit in <i>x</i><sup><i>y</i></sup> when positive integers <i>x</i> and <i>y</i> are given in binary</a> will be in P if P=PP.</p>

<p>References</p>

<p>[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen.  On the complexity of numerical analysis.  <em>SIAM Journal on Computing</em>, 38(5):1987–2006, Jan. 2009.  <a href="http://dx.doi.org/10.1137/070697926" rel="nofollow noreferrer">http://dx.doi.org/10.1137/070697926</a></p>

<p>[ADH97] Leonard M. Adleman, Jonathan DeMarrais and Ming-Deh A. Huang.  Quantum computability.  <em>SIAM Journal on Computing</em>, 26(5):1524–1540, Oct. 1997.  <a href="http://dx.doi.org/10.1137/S0097539795293639" rel="nofollow noreferrer">http://dx.doi.org/10.1137/S0097539795293639</a></p>

<p>[BV97] Ethan Bernstein and Umesh Vazirani.  Quantum complexity theory.  <em>SIAM Journal on Computing</em>, 26(5):1411–1473, Oct. 1997.  <a href="http://dx.doi.org/10.1137/S0097539796300921" rel="nofollow noreferrer">http://dx.doi.org/10.1137/S0097539796300921</a></p>

<p>[FR98] Lance Fortnow and John Rogers.  Complexity limitations on quantum computation.  <em>Journal of Computer and System Sciences</em>, 59(2):240–252, Oct. 1999.  <a href="http://dx.doi.org/10.1006/jcss.1999.1651" rel="nofollow noreferrer">http://dx.doi.org/10.1006/jcss.1999.1651</a></p>

<p>[Lau83] Clemens Lautemann.  BPP and the polynomial time hierarchy.  <em>Information Processing Letters</em>, 17(4):215–217, Nov. 1983.  <a href="http://dx.doi.org/10.1016/0020-0190(83)90044-3" rel="nofollow noreferrer">http://dx.doi.org/10.1016/0020-0190(83)90044-3</a></p>

<p>[Tiw92] Prasoon Tiwari.  A problem that is easier to solve on the unit-cost algebraic RAM.  <em>Journal of Complexity</em>, 8(4):393–397, Dec. 1992.  <a href="http://dx.doi.org/10.1016/0885-064X(92)90003-T" rel="nofollow noreferrer">http://dx.doi.org/10.1016/0885-064X(92)90003-T</a></p>

CC BY-SA 2.5
2010-10-08T11:44:10.613Z
@Tsuyoshi, The last implication (P=NP imply P=BPP) is incorrect according to this [Complexity poster, LANDSCAPE OF COMPUTATIONAL COMPLEXITY, 
Faramawi and Regan](http://www.cse.buffalo.edu/~regan/ComplexityPoster.pdf) The diagram shows that there are some problems in BPP which are not in NP. Could you please provide references?
Mohammad Al-Turkistany
CC BY-SA 2.5
2010-10-08T11:54:13.183Z
You beat me to this! Actually, you are right about BQP vs NP. There seems to be reasonable evidence that BQP is not contained in PH (see for example http://arxiv.org/abs/0910.4698), although I believe the Generalized Linial-Nisan Conjecture which is used in the second bit has since been shown to be incorrect.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-08T12:35:32.017Z
@turkistany: If I'm not mistaken, P=NP implies P=BPP because BPP is contained in PH, and if P=NP then P=PH.
Niel de Beaudrap
CC BY-SA 2.5
2010-10-08T13:02:35.423Z
Incidentally: +1 for (FP=#P)⇔(P=PP), even setting aside the rest of the content of the answer.
Niel de Beaudrap
CC BY-SA 2.5
2010-10-08T14:16:26.403Z
@Niel de Beaudrap: Yes, that is why P=NP implies P=BPP.  @turkistany: I added a reference in the answer.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-08T17:20:47.620Z
@Joe: Thanks for the comment.  Yes, BQP is not believed to be in PH, but I wonder how strongly it supports the intuitive claim “P=NP will not imply P=BQP.”  Inspired by your comment, I have posted a [related question](http://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-pnp).
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-10T14:49:46.400Z
@Joe: In light of the answers to the other question, I think that the best evidence of “P=NP does not imply P=BQP” without actually proving P=NP≠BQP would probably be an oracle separation result: “There exists an oracle A such that P^A=NP^A≠BQP^A.”  Of course, this is not easy at all because that result would imply BQP^A⊈PH^A, settling a big open question.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-10T21:01:43.203Z
@Tsuyoshi: Can't you construct such an oracle from any oracle relative to which BQP is not contained in PH, simply by taking it together with PH to form a new oracle?
Joe Fitzsimons
CC BY-SA 2.5
2010-10-10T22:17:35.020Z
@Joe: You are right!  Thanks, I did not realize that at all.
Tsuyoshi Ito
CC BY-SA 2.5
2010-10-10T22:19:56.013Z
@Tsuyoshi: No problem. It's this kind of thing that makes the site useful. I very much liked you comment about the kind of oracle separation that would be good evidence.
Joe Fitzsimons
CC BY-SA 2.5
2010-10-08T11:19:51.057Z
2010-10-08T14:14:44.657Z
2017-04-13T12:32:28.077Z
Tsuyoshi Ito
<p>Which would be the consequences of #P = FP?</p>

<p>I'm interested in both practical and theoretical consequences.</p>

<p>From a practical point of view, I'm particularly interested in consequences on Artificial Intelligence.</p>

<p>Pointers to papers or books are more than welcome.</p>

<p>Please do not say that #P = FP implies P = NP, I already know that. Also, please do not say <em>"there will be no practical consequences if the algorithm runs in time $\Omega(n^{\alpha})$, where $\alpha$ is the number of electrons in the Universe"</em>: permit me to assume that, if a deterministic polynomial time algorithm for a #P-complete problem exists, its running time will be "clement" ($O(n^2)$, for example).</p>

<cc.complexity-theory><ds.algorithms><complexity-classes><counting-complexity><ai.artificial-intel>
Consequences of #P = FP
Giorgio Camerani
# Consequences of #P = FP

(Asked by: username_0 on 2010-10-08)

Which would be the consequences of #P = FP?

I'm interested in both practical and theoretical consequences.

From a practical point of view, I'm particularly interested in consequences on Artificial Intelligence.

Pointers to papers or books are more than welcome.

Please do not say that #P = FP implies P = NP, I already know that. Also, please do not say *"there will be no practical consequences if the algorithm runs in time $\Omega(n^{\alpha})$, where $\alpha$ is the number of electrons in the Universe"*: permit me to assume that, if a deterministic polynomial time algorithm for a #P-complete problem exists, its running time will be "clement" ($O(n^2)$, for example).

**Tags:** cc.complexity-theory, ds.algorithms, complexity-classes, counting-complexity, ai.artificial-intel


---

## 3 answers

### Answer by username_5 on 2010-10-08. Score: 25 | Accepted answer

Here are a few theoretical consequences of the equality FP=#P, although they have nothing to do with artificial intelligence. The assumption FP=#P is equivalent to P=[PP](http://qwiki.stanford.edu/wiki/Complexity_Zoo:P#pp), so let me use the latter notation.

If P=PP, then we have P=[BQP](http://qwiki.stanford.edu/wiki/Complexity_Zoo:B#bqp): quantum polynomial-time computation can be simulated by classical, deterministic polynomial-time computation. This is a direct consequence of BQP⊆PP [ADH97, FR98] (and of an earlier result BQP⊆PPP [BV97]). On top of my knowledge, P=BQP is not known to follow from the assumption P=NP. This situation is different from the case of randomized computation ([BPP](http://qwiki.stanford.edu/wiki/Complexity_Zoo:B#bpp)): since BPP⊆NPNP [Lau83], the equality P=BPP follows from P=NP.

Another consequence of P=PP is that the Blum-Shub-Smale model of computation over the reals with rational constants is equvalent to Turing machines in a certain sense. More precisely, P=PP implies P=BP(Pℝ0); that is, if a language *L*⊆{0,1}\* is decidable by a constant-free program over the reals in polynomial time, then *L* is decidable by a polynomial-time Turing machine. (Here “BP” stands for “Boolean part” and has nothing to do with BPP.) This follows from BP(Pℝ0)⊆[CH](http://qwiki.stanford.edu/wiki/Complexity_Zoo:C#ch) [ABKM09]. See the paper for definitions. An important problem in BP(Pℝ0) is the [square-root sum problem](http://garden.irmacs.sfu.ca/?q=op/complexity_of_square_root_sum) and friends (e.g. “Given an integer *k* and a finite set of integer-coordinate points on the plane, is there a spanning tree of total length at most *k*?”) [Tiw92].

Similarly to the second argument, the problem of [computing a specific bit in *x**y* when positive integers *x* and *y* are given in binary](https://cstheory.stackexchange.com/questions/1811/complexity-of-exponential-function) will be in P if P=PP.

References

[ABKM09] Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen and Peter Bro Miltersen. On the complexity of numerical analysis. *SIAM Journal on Computing*, 38(5):1987–2006, Jan. 2009. <http://dx.doi.org/10.1137/070697926>

[ADH97] Leonard M. Adleman, Jonathan DeMarrais and Ming-Deh A. Huang. Quantum computability. *SIAM Journal on Computing*, 26(5):1524–1540, Oct. 1997. <http://dx.doi.org/10.1137/S0097539795293639>

[BV97] Ethan Bernstein and Umesh Vazirani. Quantum complexity theory. *SIAM Journal on Computing*, 26(5):1411–1473, Oct. 1997. <http://dx.doi.org/10.1137/S0097539796300921>

[FR98] Lance Fortnow and John Rogers. Complexity limitations on quantum computation. *Journal of Computer and System Sciences*, 59(2):240–252, Oct. 1999. <http://dx.doi.org/10.1006/jcss.1999.1651>

[Lau83] Clemens Lautemann. BPP and the polynomial time hierarchy. *Information Processing Letters*, 17(4):215–217, Nov. 1983. <http://dx.doi.org/10.1016/0020-0190(83)90044-3>

[Tiw92] Prasoon Tiwari. A problem that is easier to solve on the unit-cost algebraic RAM. *Journal of Complexity*, 8(4):393–397, Dec. 1992. <http://dx.doi.org/10.1016/0885-064X(92)90003-T>

> **Comments:**
> **username_2**: @Tsuyoshi, The last implication (P=NP imply P=BPP) is incorrect according to this [Complexity poster, LANDSCAPE OF COMPUTATIONAL COMPLEXITY,  Faramawi and Regan](http://www.cse.buffalo.edu/~regan/ComplexityPoster.pdf) The diagram shows that there are some problems in BPP which are not in NP. Could you please provide references?  
> **username_6**: You beat me to this! Actually, you are right about BQP vs NP. There seems to be reasonable evidence that BQP is not contained in PH (see for example http://arxiv.org/abs/0910.4698), although I believe the Generalized Linial-Nisan Conjecture which is used in the second bit has since been shown to be incorrect.  
> **username_3**: @turkistany: If I'm not mistaken, P=NP implies P=BPP because BPP is contained in PH, and if P=NP then P=PH.  
> **username_3**: Incidentally: +1 for (FP=#P)⇔(P=PP), even setting aside the rest of the content of the answer.  
> **username_5**: @username_3: Yes, that is why P=NP implies P=BPP.  @turkistany: I added a reference in the answer.  
> **username_5**: @Joe: Thanks for the comment.  Yes, BQP is not believed to be in PH, but I wonder how strongly it supports the intuitive claim “P=NP will not imply P=BQP.”  Inspired by your comment, I have posted a [related question](http://cstheory.stackexchange.com/questions/2032/a-decision-problem-which-is-not-known-to-be-in-ph-but-will-be-in-p-if-pnp).  
> **username_5**: @Joe: In light of the answers to the other question, I think that the best evidence of “P=NP does not imply P=BQP” without actually proving P=NP≠BQP would probably be an oracle separation result: “There exists an oracle A such that P^A=NP^A≠BQP^A.”  Of course, this is not easy at all because that result would imply BQP^A⊈PH^A, settling a big open question.  
> **username_6**: @Tsuyoshi: Can't you construct such an oracle from any oracle relative to which BQP is not contained in PH, simply by taking it together with PH to form a new oracle?  
> **username_5**: @Joe: You are right!  Thanks, I did not realize that at all.  
> **username_6**: @Tsuyoshi: No problem. It's this kind of thing that makes the site useful. I very much liked you comment about the kind of oracle separation that would be good evidence.  

---

### Answer by username_1 on 2010-10-08. Score: 15

In [graphical models](http://en.wikipedia.org/wiki/Graphical_model), many of the estimation problems are #P-complete, because they involve doing sum-product calculations a la the permanent over general graphs. If #P = FP, then graphical models suddenly get a whole lot easier, and we don't have to muck around with low-treewidth models anymore.


---

### Answer by username_2 on 2010-10-08. Score: 5

Toda proved that any problem in the polynomial-time hierarchy can be reduced to #P function. Formally, he proved that $PH \subseteq P^{\#P}$. So if $\sharp P=FP$ then the $PH$ would collapse and consequently Tautologies would have short proofs.

> **Comments:**
> **username_1**: i think it's a typo for polynomial.  
> **username_3**: Can someone clarify: is this not the same as saying "P=PH" (which would immediately follow from P=NP)?  
> **username_0**: @Niel: It's not the same, it is stronger.  
> **username_3**: @Walter: in what way? Is not $\text P^{\text{FP}} = \text P$? If so, then $\#\text P = \text{FP}$ would imply $\text{PH} \subseteq \text P^{\#\text P} = \text P^{\text{FP}} = \text P \subseteq \text{PH}$.  
> **username_0**: @Niel: Sorry, I read your first comment too quickly and I completely misunderstood your question. Of course what you said is right. What I meant in my comment was the very obvious fact that #P = FP is a stronger statement than P = NP.  
> **username_3**: @All: just to clarify --- my first comment above was asking the following question *"Is turkistany's answer equivalent to the statement that FP=#P implies P=PH?"* If I wanted to know whether FP=#P was equivalent to P=PH, I would have asked this in a comment on the original post, not on turkistany's answer.  
> **username_4**: @Niel: You're right. This is the same as saying P = PH, which follows from P = NP. Therefore the use of Toda's theorem was not necessary, since FP = #P already implies P = NP = PH.  

---

