Hard constraint satisfaction problems have hard gaps at location 1

Peter Jonsson, Andrei Krokhin, Fredrik Kuivinen

An instance of Max CSP is a finite collection of constraints on a set of variables, and the goal is to assign values to the variables that maximises the number of satisfied constra…