In this paper, we study the approximability of Max CSP(P) where P is a Boolean predicate. We prove that assuming Khot's d-to-1 Conjecture, if the set of accepting inputs of P strictly contains all inputs with even (or odd) parity, then it is NP-hard to approximate Max CSP(P) better than the simple random assignment algorithm even on satisfiable instances. This is a generalization of a work by O'Donnell and Wu which proved that it is NP-hard to approximate satisfiable instances of Max CSP(NTW) beyond 85+ for any 0 based on Khot's d-to-1 Conjecture, where NTW is the ``Not Two'' predicate of size 3.
展开▼
