Now we show α(v) ≤Se ve.
$\alpha$ we show $\alpha(v)$ -$\alpha$.  By $v<_{S}\overline{v}$, we have $\alpha(v)\leq_{S}\alpha(\overline{v})$. Then
$$\widetilde{v}=\widetilde{\sum_{i=1}^{n}\prod_{j=1}^{m}}\alpha(v_{ij})$$ $$=\alpha(\sum_{i=1}^{n}\prod_{j=1}^{m}v_{ij})$$ $$=\alpha(v)\leq_{\widetilde{S}}\alpha(\overline{v})=\alpha(\sum_{i=1}^{n}\prod_{j=1}^{m}u_{ij})=\widetilde{\sum_{i=1}^{n}\prod_{j=1}^{m}}\alpha(u_{ij})=\widetilde{\overline{v}}$$
where the last term, ev, is the value of t¯ in α(P). Now since t **is optimal in** α(P),
we have ve = α(v) = α(v) = ev. That is, t¯ is also optimal in α(P**) with value**
ve.

Remark 5.1. **If our aim is to find some instead of all optimal solutions of the** concrete problem P**, by Theorem 5.1 we could first find all optimal solutions** of the abstract problem α(P), and then compute their values in P**, tuples that** have maximal values in P are optimal solutions of P**. In this sense, this theorem** is more desirable than Theorem 4.1 because we do not need the assumption that α **is order-reflecting.**
Theorem 5.1 can also be applied to find good approximations of the optimal solutions of P. Given an optimal solution t ∈ Opt(α(P)) with value ˜v ∈ Se**, then**
by Theorem 5.1 there is an optimal solution t¯ ∈ Opt(P**) with value in the set**
{u ∈ S : α(u) = ve}.

Note that Theorem 5.1 requires α **to be a semiring homomorphism. This**
condition is still a little restrictive. Take the probabilistic semiring S**prop** = h[0, 1], max, ×, 0, 1i and the classical semiring SCSP = h{T, F}, ∨, ∧**, F, T** i as example, there are no nontrivial homomorphisms between Sprop and SCSP **. This**
is because α(a × b) = α(a) ∧ α(b**) requires** α(a n) = α(a) for any a ∈ [0, **1] and**
any positive integer n, which implies (∀a > 0)α(a) = 1 or (∀a < 1)α(a**) = 1.**
In the remainder of this section, we relax this condition.

Definition 5.1 (quasi-homomorphism). A mapping ψ **from semiring** hS, +, ×,
0, 1i to semiring hS, e +e, ×e, 0e, 1ei **is said to be a** *quasi-homomorphism* **if for any**
a, b ∈ S
- ψ(0) = 0e, ψ(1) = 1e**; and**
- ψ(a + b) = ψ(a)+eψ(b**); and** - ψ(a × b) ≤Se ψ(a)×eψ(b).

The last condition is exactly the *locally correctness* of ×e w.r.t. × **[1].**
Clearly, each monotonic surjective mapping between Sprop and SCSP **is a quasihomomorphism.**
The following theorem shows that a quasi-homomorphism is also useful.