Proposition

Proposition 2 ([Affine 2-to-1 Games Theorem]). For every constant b∈(0,1) there is an integer n≥1 such that, for every constant a∈(0,1-b) , the following promise problem is NP-hard. Its input is a weighted bipartite game with vertex sets …

Proposition 2 ([Affine 2-to-1 Games Theorem]). For every constant b∈(0,1) there is an integer n≥1 such that, for every constant a∈(0,1-b) , the following promise problem is NP-hard. Its input is a weighted bipartite game with vertex sets X,Y , respective label setsⁿ+1 ,ⁿ , and a surjective affine map π_e:ⁿ+1 ⟶ⁿ on each edge e=(x,y) . An edge is satisfied when π_e(λ_X(x))=λ_Y(y) . The promise cases are YES: ( G)≥1-a, NO: ( G)≤b. The integer n depends on b alone. For fixed a,b , the reduction is deterministic and has polynomial running time and output size.