Clearly, all alignments can be encoded using at most p (| (f , e) |) bits.
if (f , e) computes P (f |e) and hence, PROBABILITY-3 is in #P. It follows immediately from Lemma 2 and Lemma 3 that Theorem 1 PROBABILITY-3 is #P-Complete.