Definition 2.9 (projection [3]). **Given a constraint** c = hdef, coni **and a subset**
I of V **, the** *projection* of c over I, denoted by c ⇓I **, is the constraint** hdef′, con′i where con′ = con ∩ I and def′(t
′) = P{def(t) : t| con con∩I = t
′}**. Particularly, if** I =
∅, then c ⇓∅: {ε} → S **maps 0-tuple** ε to P{def(t) : t **is a tuple with type** con},
which is the sum of the values associated to all |con|**-tuples.**
Now the concept of solution can be defined as the projection of the **combination of all constraints over the type of the problem.**
Definition 2.10 (solution and optimal solution). The *solution* **of an SCSP** P = hC, coni **is a constraint of type** con **which is defined as:**

## Sol(P**) = (**C ∗ × Oc) ⇓Con (1)

where c
∗**is the maximal constraint with type** con.

Write Sol(P) = hdef, coni, a |con|-tuple t **is an** *optimal solution* of P if def(t)
is maximal, that is to say there is no t
′**such that** def(t
′) >S def(t**). We write**
Opt(P) for the set of optimal solutions of P**. For any** |con|-tuple t**, we also write** Sol(P)(t**) for** def(t).

## 3 Translation And Semiring Homomorphism

Let S = hS, +, ×, 0, 1i and Se = hS, e +e, ×e, e0, 1ei **be two c-semirings and let** α :
S → Se be an arbitrary mapping from S to Se. Also let D **be a nonempty finite**
set and let V **be an ordered set of variables. Fix a type** con ⊆ V **. We now**
investigate the relation between problems over S **and those over** Se.

Definition 3.1 (translation). Let P = hC, coni be an SCSP over S **where**
C = {c0, · · · , cn}, ci = hdefi, conii**, and** defi: D|coni| → S**. By applying** α to each constraints respectively, we get an SCSP hC, e coni over Se**, called the** α-*translated problem* of P, which is defined by Ce = {ce1 **· · ·** cen}, cei = hdef gi, conii, and def gi = α ◦ defi: D|coni| → Se.

![0_image_0.png](0_image_0.png)

We write α(P) for the α**-translated problem of** P.
Without loss of generality, in what follows we assume α(0) = 0e, and α(1) =
1e**. We say** α *preserves problem ordering*, if for any two SCSPs P, Q over S**, we**
have Sol(P) ⊑S Sol(Q) ⇒ Sol(α(P)) ⊑Se Sol(α(Q**)) (2)**
The following theorem then characterizes when α **preserves problem ordering.**