= Solution
For the intended finite representation, put $m=|S|<\infty$. For each $T\subseteq S$, form the <minterm>
$$
\chi_T=
\left(\bigwedge_{s_i\in T}x_i\right)\land
\left(\bigwedge_{s_i\notin T}\neg x_i\right).
$$
A <Boolean valuation> satisfies $\chi_T$ exactly when its selected subset is $T$. Therefore the <weighted formula utility representation>
$$
\mathcal R_u=\{(\chi_T,u(T)):T\subseteq S\}
$$
represents $u$ exactly: at the <Boolean valuation> for $T$, only that <minterm> contributes, with weight $u(T)$. This proves \b[completeness and the bound of $2^{|S|}$ rules] simultaneously. Zero-weight rules may be omitted. The bound counts rules; writing each <minterm> also requires $O(m)$ symbols in <Big O notation>.
For the computational question, assume rule weights are <rational numbers> encoded in binary. This makes exact equality of sums a finite computational task. With this conventional encoding, \b[equivalence of <weighted formula utility representations> is <co-NP>-complete].
For membership, the complement has a short witness: a <Boolean valuation> on the variables occurring in either rule base. Evaluate each <propositional formula>, sum the weights of satisfied rules, and accept the witness if the sums differ. <Propositional formula> evaluation takes <polynomial time>. Exact sums of binary <rational numbers> also have polynomially bounded bit lengths: the product of their denominators has bit length at most the sum of the input denominator lengths. Thus non-equivalence lies in <NP>, and equivalence lies in <co-NP>.
For hardness, take a <Boolean satisfiability problem> instance $\theta$ and construct
$$
\mathcal R_1=\{(\theta,1)\},\qquad \mathcal R_2=\varnothing.
$$
The first <utility function> is one at satisfying <Boolean valuations> and zero elsewhere, while the second is always zero. Consequently
$$
\mathcal R_1\equiv\mathcal R_2
\iff \theta\text{ is an unsatisfiable Boolean formula}.
$$
The <unsatisfiable Boolean formula> problem is <co-NP>-complete, as the complement of the <NP>-complete <Boolean satisfiability problem>. The construction is a <polynomial-time reduction>, proving hardness even with the single weight $1$.
Two qualifications matter in the literal wording. First, unrestricted real weights have no specified finite encoding, so a standard bit-complexity classification needs the encoding assumption above. Second, the problem says only that $S$ is nonempty. If infinite $S$ is allowed while rule bases remain finite, its completeness claim is false. For $S=\mathbb N$, take $u(T)=1$ when $T$ is infinite and $u(T)=0$ when $T$ is finite. A finite rule base mentions only a finite subset $F$ of the variables. The <Boolean valuations> for $\varnothing$ and $\mathbb N\setminus F$ agree on all those variables but have different required values. No such rule base represents this $u$. Thus the construction answers the intended finite-set question and identifies the missing hypothesis in the unrestricted statement.
Back to article page
