Lemma 7 (j, i, m, l)-COUNT-3 is in #P. Proof: Similar to the proof of Lemma 5. times in e. Replace these k occurrences by only one occurrence of e i and connect all the words connected to them to this word.
this would increase the score of e by a factor of 2 k−1 > 1 contradicting the assumption on the optimality of e. the only candidates for e are subsets of {e 1 , e 2 , .