skip to content

CSP and MMSNP are computationally equivalent

Presented by: 
G Kun [Eotvos]
Monday 13th March 2006 - 11:00 to 12:00
INI Seminar Room 1

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.

University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons