The FO Model Counting problem (FOMC) is the following: given a sentence
$\Phi$ in FO and a number $n$, compute the number of models of $\Phi$ over a
domain of size $n$; the Weighted variant (WFOMC) generalizes the problem by
associating a weight to each tuple and defining the weight of a model to be the
product of weights of its tuples. In this paper we study the complexity of the
symmetric WFOMC, where all tuples of a given relation have the same weight. Our
motivation comes from an important application, inference in Knowledge Bases
with soft constraints, like Markov Logic Networks, but the problem is also of
independent theoretical interest. We study both the data complexity, and the
combined complexity of FOMC and WFOMC. For the data complexity we prove the
existence of an FO$^{3}$ formula for which FOMC is #P$_1$-complete, and the
existence of a Conjunctive Query for which WFOMC is #P$_1$-complete. We also
prove that all $\gamma$-acyclic queries have polynomial time data complexity.
For the combined complexity, we prove that, for every fragment FO$^{k}$, $k\geq
2$, the combined complexity of FOMC (or WFOMC) is #P-complete.

在本文中，我们研究了对称加权有限模型计数问题的复杂性，旨在解决知识库推理中的软约束问题。我们证明了特定情况下该问题的数据复杂度可在多项式时间内计算，但在一般情况下该问题在 #P 中是完全的复杂度。