An Isaac Newton Institute Programme

Logic and Algorithms

CSP and MMSNP are computationally equivalent

13th March 2006

Author: Gabor Kun (Eotvos University)

Abstract

We introduce the notion of expander hypergraphs as one natural generalisation of expander graphs. We give an efficient construction of expander hypergraphs. This new tool makes possible to derandomise Feder and Vardi's reduction of CSP to large girth CSP. This implies the derandomisation of the computational equivalence between the classes CSP and MMSNP (Monotone monadic SNP).

Theorem: For every language L in MMSNP there are relational structures S1, ... ,Sn such that the following hold.

(1) L has a polynomial reduction to the union of the languages CSP(Si). (2) For every i the language CSP(Si) has a polynomial reduction to L.