A new algorithm for optimal 2-constraint satisfaction and its implications

摘要: We present a novel method for exactly solving (in fact, counting solutions to) general constraint satisfaction optimization with at most two variables per (e.g. MAX-2-CSP and MIN-2-CSP), which gives the first exponential improvement over trivial algorithm. More precisely, runtime bound is constant factor in base of exponent: algorithm can count number optima MAX-2-SAT MAX-CUT instances O(m32ωn/3) time, where ω < 2.376 matrix product exponent ring. When constraints have arbitrary weights, there (1 + e)-approximation roughly same runtime, modulo polynomial factors. Our construction shows that either k-clique solution (even when k = 3) or multiplication GF(2) would improve 2-CSP optimization.Our approach also yields connections between complexity some (polynomial time) high-dimensional search problems NP-hard problems. For example, if are sufficiently faster algorithms computing diameter n points l1, then an (2 - e)n MAX-LIN. These results may be construed as lower bounds on problems, hope better exist corresponding hard