26
$\begingroup$

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

$\endgroup$

3 Answers 3

25
$\begingroup$

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(P0); 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(P0)⊆CH [ABKM09]. See the paper for definitions. An important problem in BP(P0) 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

$\endgroup$
10
  • 4
    $\begingroup$ 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 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. $\endgroup$ Oct 8, 2010 at 11:54
  • 9
    $\begingroup$ @turkistany: If I'm not mistaken, P=NP implies P=BPP because BPP is contained in PH, and if P=NP then P=PH. $\endgroup$ Oct 8, 2010 at 12:35
  • 1
    $\begingroup$ Incidentally: +1 for (FP=#P)⇔(P=PP), even setting aside the rest of the content of the answer. $\endgroup$ Oct 8, 2010 at 13:02
  • 2
    $\begingroup$ @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. $\endgroup$ Oct 10, 2010 at 14:49
  • 2
    $\begingroup$ @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? $\endgroup$ Oct 10, 2010 at 21:01
15
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
7
  • 4
    $\begingroup$ Can someone clarify: is this not the same as saying "P=PH" (which would immediately follow from P=NP)? $\endgroup$ Oct 8, 2010 at 7:53
  • 1
    $\begingroup$ @Niel: It's not the same, it is stronger. $\endgroup$ Oct 8, 2010 at 8:12
  • 3
    $\begingroup$ @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}$. $\endgroup$ Oct 8, 2010 at 8:21
  • 1
    $\begingroup$ @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. $\endgroup$ Oct 8, 2010 at 13:07
  • 2
    $\begingroup$ @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. $\endgroup$ Oct 8, 2010 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy