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.