Skip to content



CSP and MMSNP are computationally equivalent

Kun, G (Eotvos)
Monday 13 March 2006, 11:00-12:00

Seminar Room 1, Newton Institute


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.

Back to top ∧