The Complexity of the Homomorphism Problem for Boolean structures.

We show that for a fixed Boolean structure $\mathscr B$ of arbitrary finite signature---i.e., not necessarily purely relational---the problem of deciding whether there exists a homomorphism to $\mathscr B$ is either in P or NP-complete.

Logic, Reasoning, and Knowledge semigroups and automata theory Logic, programming, and type systems Computer Science Mathematics

View graph Source

Paper

Similar papers

The Complexity of Homomorphism ReconstructibilityJan Böker, Louis Härtel, Nina Runde et al.2023 · arXiv (Cornell University) In Library

On Logics and Homomorphism ClosureManuel Bodirsky, Thomas Feller, Simon Knäuer et al.2021 In Library

Complexity of Homogeneous Co-Boolean Constraint Satisfaction ProblemsFlorian Richoux2010 · Pacific-Asia Conference on Circuits, Communications and Systems · 0 citations In Library

Fractional homomorphism, Weisfeiler-Leman invariance, and the Sherali-Adams hierarchy for the Constraint Satisfaction ProblemSilvia Butti, V. Dalmau2021 · International Symposium on Mathematical Foundations of Computer Science · 12 citations In Library

Constraint Satisfaction Problems over Finitely Bounded Homogeneous Structures: a Dichotomy between FO and L-hardLeonid Dorochko, Michal Wrona2026 · arXiv.org · 0 citations In Library

Polyadic Sets and Homomorphism CountingLuca Reggio2021 · arXiv (Cornell University) In Library

The algebraic dichotomy conjecture for infinite domain Constraint Satisfaction ProblemsL. Barto, M. Pinsker2016 · Logic in Computer Science · 89 citations In Library

When symmetries are not enough: a hierarchy of hard Constraint Satisfaction ProblemsPierre Gillibert, Julius Jonusas, M. Kompatscher et al.2020 · SIAM journal on computing (Print) · 15 citations In Library

Horn versus full first-order: Complexity dichotomies in algebraic constraint satisfactionM. Bodirsky, Peter Jonsson, T. Oertzen2010 · Journal of Logic and Computation · 14 citations In Library

Constraint satisfaction problems for reducts of homogeneous graphsM. Bodirsky, Barnaby Martin, M. Pinsker et al.2016 · International Colloquium on Automata, Languages and Programming · 57 citations In Library

Source of record

OpenAlex

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal