World Colleges Information

We present algebraic conditions on constraint languages 􀀀 that ensure the hardness of the constraint satisfaction problem CSP.􀀀 / for complexity classes L, NL, P, NP and ModpL. These criteria also give non-expressibility results for various restrictions of Datalog. Furthermore, we show that if CSP.􀀀 / is not first-order definable then it is L-hard.