Forbidden lists (NP and CSP for combinatorialists)

Gabor Kun, Jaroslav Nesetril

We present a definition of the class NP in combinatorial context as the set of languages of structures defined by finitely many forbidden lifted substructures. We apply this to spe…