William DeMeo

Complexity of the Homomorphism Problem for Boolean Models


I describe some recent joint work with Antoine Mottet and Libor Barto in which we prove that for a fixed boolean structure B of arbitrary finite signature—i.e., not necessarily purely relational—the problem of deciding whether there exists a homomorphism into B is either in P or NP-complete.

Slides available at https://gitpitch.com/UniversalAlgebra/hom-csp?grs=gitlab#/1.