= Equivalence of weighted formula utility representations
Given two <weighted formula utility representations> with binary <rational numbers> as weights, decide whether their values agree on every <Boolean valuation>. This problem is <co-NP>-complete.
For membership, a valuation witnessing unequal values certifies non-equivalence. Evaluate all <propositional formulas> and add their weights exactly in <polynomial time>. For hardness, compare the one-rule base $\{(\theta,1)\}$ with the empty base. They are equivalent exactly when $\theta$ is an <unsatisfiable Boolean formula>. Thus even very small weighted rule bases express a universal equivalence question.
Back to article page
