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$
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$
  • 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$ – Joe Fitzsimons Oct 8 '10 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$ – Niel de Beaudrap Oct 8 '10 at 12:35
  • 1
    $\begingroup$ Incidentally: +1 for (FP=#P)⇔(P=PP), even setting aside the rest of the content of the answer. $\endgroup$ – Niel de Beaudrap Oct 8 '10 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$ – Tsuyoshi Ito Oct 10 '10 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$ – Joe Fitzsimons Oct 10 '10 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$
  • 4
    $\begingroup$ Can someone clarify: is this not the same as saying "P=PH" (which would immediately follow from P=NP)? $\endgroup$ – Niel de Beaudrap Oct 8 '10 at 7:53
  • 1
    $\begingroup$ @Niel: It's not the same, it is stronger. $\endgroup$ – Giorgio Camerani Oct 8 '10 at 8:12
  • 2
    $\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$ – Niel de Beaudrap Oct 8 '10 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$ – Niel de Beaudrap Oct 8 '10 at 13:07
  • 1
    $\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$ – Robin Kothari Oct 8 '10 at 13:24

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.