We prove that, for any ∈ > 0, it is NP-hard to, given a satis-fiable instance of Max-NTW (Not-2), find an assignment that satisfies a fraction 5/8 + ∈ of the constraints. This, up to the existence of ∈, matches the approximation ratio obtained by the trivial algorithm that just picks an assignment at random and thus the result is tight. Said equivalently the result proves that Max-NTW is approximation resistant on satisfi-able instances and this makes our understanding of arity three Max-CSPs with regards to approximation resistance complete.
展开▼
