

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

## 3.2 Hardness For Value-Based Systems Of Value-Width 2

This subsection is devoted to prove Theorem 1. We devise a polynomial reduction from 3SAT. Let Φ be a 3CNF
formula with clauses C1**, . . . , C**m and Cj = xj,1 ∨ xj,2 ∨ xj,3 for 1 ≤ j ≤ m. In the following we construct a value-based system F = (**X, A, V, η**) of value-width 2 and attack-width 1 such that the query argument x1 ∈ X
is subjectively accepted in F if and only if Φ is satisfiable. See Figure 4 for an example.

The set X contains the following arguments:
1. a pair of arguments xj , zj for 1 ≤ j ≤ m; 2. a pair of arguments x i j
, zij for 1 ≤ j ≤ m and 1 ≤ i ≤ 3; 3. an argument t.

The set A contains the following attacks:
1. (z1, x1);
2. (x i j
, zj ) and (z i j
, xj ) for 1 ≤ j ≤ m and 1 ≤ i ≤ 3; 3. (xj+1, zij
) and (zj+1, xij
) for 1 ≤ j ≤ m − 1 and 1 ≤ i ≤ 3; 4. (**t, z**im) for 1 ≤ i ≤ 3; 5. (x i j
, xi
′

j
′ ) for 1 ≤ j
′ < j ≤ m and 1 ≤ **i, i**′ ≤ 3 whenever xj,i and xj
′
,i′ are complementary literals.

The set V contains one value for each **x, z** pair, and one value for argument t, i.e., |V | = 4m + 1. Consequently, the mapping η is defined such that η(xj ) = η(zj ) = vj , η(x i j
) = η(z i j
) = v i j for 1 ≤ j ≤ m, 1 ≤ i ≤ 3, and