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.