The next lemma shows that α **preserves optimal solutions only if it is a**
semiring homomorphism.

Lemma 4.3. Let α be a mapping from c-semiring S to c-semiring Se *such that* α(0) = 0e, α(1) = 1e. Suppose α : S → Se *preserves optimal solutions. Then* α is a semiring homomorphism. Proof. By Lemma 4.1, we know α **satisfies Equation 5. We first show that** α is monotonic. Take u, v ∈ S, u ≤S v. Suppose α(u) 6≤Se α(v). Then α(v)+eα(v) =
α(v) <Se α(u)+eα(v). By Equation 5, we have v = v + v <S u + v = v**. This is a**
contradiction, hence we have α(u) ≤Se α(v).

Next, for any u, v ∈ S, we show α(u+v) = α(u)+eα(v). Since α **is monotonic,**
we have α(u + v) ≥Se α(u)+eα(v). Suppose α(u + v)+eα(u + v) = α(u + v) >Se α(u)+eα(v). By Equation 5 again, we have (u + v) + (u + v) >S u + v**, also a**
contradiction.

Finally, for u, v ∈ S, we show α(u × v) = α(u)×eα(v**). Suppose not and set**
w = α(u)×eα(v)+eα(u×v**). Then we have either** α(u)×eα(v) <Se w or α(u×v) <Se w. Since α(0) = e0, α(1) = 1e**, these two inequalities can be rewritten respectively**
as α(u)×eα(v) + α(1)×eα(0) <Se α(u)×eα(v)+eα(u × v)×eα(1e)
and α(1)×eα(0) + α(u × v)×eα(1) <Se α(u)×eα(v)+eα(u × v)×eα(1e).

By Equation 5 again, we have either u × v + 1 × 0 <S u × v + (u × v) × 1 or 1 × 0 + (u × v) × 1 <S u × v + (u × v) × 1**. Both give rise to a contradiction.**
This ends the proof.

We now achieve our main result:
Theorem 4.1. Let α be a mapping from c-semiring S to c-semiring Se *such* that α(0) = 0e, α(1) = e1. Then α preserves optimal solutions for all constraint systems if and only if α is an order-reflecting semiring homomorphism. Proof. **The necessity part of the theorem follows from Lemmas 4.2 and 4.3. As** for the sufficiency part, we need only to show that, if α **is an order-reflecting** semiring homomorphism, then α **satisfies Equation 5. Suppose**

$$\widetilde{\sum}_{i=1}^{-n}\widetilde{\prod}_{j=1}^{m}\alpha(u_{i j})<_{\widetilde{S}}\widetilde{\sum}_{i=1}^{-n}\widetilde{\prod}_{j=1}^{m}\alpha(v_{i j}).$$
Clearly we have $\frac{1}{2}$
Clearly we have  $$\alpha(\sum_{i=1}^{n}\prod_{j=1}^{m}u_{ij})=\widetilde{\sum}_{i=1}^{n}\widetilde{\prod}_{j=1}^{m}\alpha(u_{ij})<_{\widetilde{S}}\widetilde{\sum}_{i=1}^{n}\widetilde{\prod}_{j=1}^{m}\alpha(v_{ij})=\alpha(\sum_{i=1}^{n}\prod_{j=1}^{m}v_{ij})\,$$  since $\alpha$ commutes with $\sum$ and $\prod$. By order-reflecting, we have immediately  $$\sum_{i=1}^{n}\prod_{j=1}^{m}u_{ij}<_{S}\sum_{i=1}^{n}\prod_{j=1}^{m}v_{ij}.$$  This ends the proof.  
$\square$
$$10$$
