26

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).

Giorgio Camerani
  • 6,842
  • 1
  • 34
  • 64

3 Answers3

25

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, so let me use the latter notation.

If P=PP, then we have P=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): 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 [ABKM09]. See the paper for definitions. An important problem in BP(Pℝ0) is the square-root sum problem 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 xy when positive integers x and y are given in binary 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

Community
  • 1
Tsuyoshi Ito
  • 16,466
  • 2
  • 55
  • 106
  • @Tsuyoshi, The last implication (P=NP imply P=BPP) is incorrect according to this Complexity poster, LANDSCAPE OF COMPUTATIONAL COMPLEXITY, Faramawi and Regan The diagram shows that there are some problems in BPP which are not in NP. Could you please provide references? – Mohammad Al-Turkistany Oct 08 '10 at 11:44
  • 4
    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 Oct 08 '10 at 11:54
  • 9
    @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 Oct 08 '10 at 12:35
  • 1
    Incidentally: +1 for (FP=#P)⇔(P=PP), even setting aside the rest of the content of the answer. – Niel de Beaudrap Oct 08 '10 at 13:02
  • @Niel de Beaudrap: Yes, that is why P=NP implies P=BPP. @turkistany: I added a reference in the answer. – Tsuyoshi Ito Oct 08 '10 at 14:16
  • @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. – Tsuyoshi Ito Oct 08 '10 at 17:20
  • 2
    @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 Oct 10 '10 at 14:49
  • 2
    @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 Oct 10 '10 at 21:01
  • @Joe: You are right! Thanks, I did not realize that at all. – Tsuyoshi Ito Oct 10 '10 at 22:17
  • @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 Oct 10 '10 at 22:19
15

In graphical models, 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.

Suresh Venkat
  • 32,071
  • 4
  • 95
  • 271
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.

Mohammad Al-Turkistany
  • 20,928
  • 5
  • 63
  • 149
  • i think it's a typo for polynomial. – Suresh Venkat Oct 08 '10 at 07:49
  • 4
    Can someone clarify: is this not the same as saying "P=PH" (which would immediately follow from P=NP)? – Niel de Beaudrap Oct 08 '10 at 07:53
  • 1
    @Niel: It's not the same, it is stronger. – Giorgio Camerani Oct 08 '10 at 08:12
  • 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}$. – Niel de Beaudrap Oct 08 '10 at 08:21
  • @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 Oct 08 '10 at 10:24
  • 1
    @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 Oct 08 '10 at 13:07
  • 2
    @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 Oct 08 '10 at 13:24