

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

$$\langle s,a\rangle.$$

## H(Π) = H**S, A**I.

Provided that the polynomial hierarchy does not collapse, a problem is not in k❀**P if**
there exists a monotonic Polynomial reduction from 3sat **to the problem (Liberatore, 2001).**
A polynomial reduction is monotonic if the two functions it is made of satisfy the following condition: for every pair of sets of clauses Π1 and Π2 **of three literals over the same set of** variables, if Π1 ⊆ Π2 then hr(Π1), h(Π1)i is a "yes" instance if and only if hr(Π2), h(Π1)i is a "yes" instance. Note that the second instance is hr(Π2), h(Π1)i**, that is, it combines a**
part derived from Π2 **and a part from Π**1.

The specialization of this condition to the case of the next-action problem is as follows.

Let hM1, Ti = r(Π1) and hM2, Ti = r(Π2): the two horizons are the same because Π1 and Π2 are on the same alphabet. Let hs, ai = h(Π1**). Monotonicity holds if, for any two sets** of clauses Π1 and Π2 over the same set of literals with Π1 ⊆ Π2, a **is the optimal action to** execute in the state s for M1 and T if and only if it is so for M2 and T**. The reduction** f defined above satisfies this condition.

Theorem 2 The function f from sets of clauses to quadruples hM, T, s, ai **is a monotonic**
polynomial reduction.

Proof. Let Π1 and Π2 **be two sets of clauses over the same set of variables, each clause being**
composed of three literals, and let M1 and M2 **be their corresponding MDPs. Since the**
MDP corresponding to a set of clauses depends—by construction—on the set of variables only, M1 and M2 are exactly the same MDP. Since the horizons of r(Π1) and r(Π2**) are** the same, we have r(Π1) = r(Π2). As a result, for any state s and action a**, the latter is the** optimal action to execute in M1 for the horizon T if and only if it is so for M2**, and this is**
the definition of monotonicity for the case of MDPs.