A Gap Trichotomy for Boolean Constraint Problems: Extending Schaefer's Theorem
Marcel Jackson · arXiv (Cornell University) · 2015
In this paper, we examine some flexible notions of constraint satisfaction, observing some relationships between model theoretic notions of universal Horn class membership and robust satisfiability. We show the NP-completeness of 2-robust positive 1-in-3SAT in order to give very small examples of finite algebras with NP-hard variety membership problem. In particular, we give a 3-element algebra with this property, and solve a widely stated problem by showing that the 6-element Brandt monoid has NP-hard variety membership problem. These are the smallest possible sizes for a general algebra and a semigroup to exhibit NP-hardness for the membership problem of finite algebras in finitely generated varieties.