complexity than the initial formula after the formula being spitted. The characteristic polynomial of the branching vector is defined as follows:

$$\mathrm{h}(x)=1-\sum_{i=1}^{k}x^{-r_{i}}$$

$$\mathbf{(1)}$$

The positive root of this polynomial is called the branching number, denoted by(r1, r2,…, rk). And we assume that the branching number of the leaves is 1. The maximum branching numbers of nodes is defined as the branching number of the branching tree, expressed by max(r1, r2,…, rk). Actually, the branching number of a branching tree has an important relationship with the running time (T(n)) of a DPLL-style algorithm. At first, assume the running time of a DPLL-style algorithm performing on each node is in polynomial time. Then the following inequality is obtained.

T(n)(max(r1, r2,…, rk)) npoly(F)
(2)

$$=(\operatorname*{max}\sum_{i=1}^{k}\mathrm{T}(n\text{-}r_{\mathrm{i}}))^{n}\times\operatorname{poly}(F)$$
1
i
where n is the number of variables in F, ploy(F) is the polynomial time executing on the node F, and

$$({\mathfrak{I}})$$
$$\lambda\ (r_{1},r_{2},\ldots,r_{k})=\sum_{i=1}^{k}\mathrm{T}(n\mbox{-}r_{\mathrm{i}})$$

In addition, if a \#XSAT problem recursively solved by a DPLL-style algorithm, the time required doesn't increase, for

$\sum_{i=1}^{k}\Gamma(n_{i})\leq\Gamma(n)$ where $n=\sum_{i=1}^{k}n_{i}$ (4)
where n is the number of variables, niis the number of variables in the sub-formula Fi (1ik) of the formula F. Note that when analyzing the running time, we ignore the polynomial factor so that we assume that all polynomial time computations take O(1) time in this paper.

## Algorithm For Solving #Xsat

In this section, we present the algorithm \#XSAT for counting models of the exact satisfiability problem and prove an upper bound O(1.1995n). Firstly we address some principles used in this part.