关键词：最大约束满意度问题；组合最优问题；编程
摘 要：Maximum constraint satisfaction problem (Max-CSP) is a rich class of combinatorial optimization problems. In this dissertation, we show optimal (up to a constant factor) NPhardness for maximum constraint satisfaction problem with k variables per constraint (Max- k-CSP), whenever k is larger than the domain size. This follows from our main result concerningCSPs given by a predicate: a CSP is approximation resistant if its predicate containsa subgroup that is balanced pairwise independent. Our main result is related to previous works conditioned on the Unique-Games Conjecture and integrality gaps in sum-of squares semide nite programming hierarchies.