{
  "id": "1512.03127",
  "version": "v1",
  "published": "2015-12-10T02:31:37.000Z",
  "updated": "2015-12-10T02:31:37.000Z",
  "title": "Flexible constraint satisfiability and a problem in semigroup theory",
  "authors": [
    "Marcel Jackson"
  ],
  "categories": [
    "math.LO",
    "cs.CC",
    "cs.LO",
    "math.CO"
  ],
  "abstract": "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 \\texttt{NP}-completeness of $2$-robust monotone 1-in-3 3SAT in order to give very small examples of finite algebras with \\texttt{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 \\texttt{NP}-hard variety membership problem. These are the smallest possible sizes for a general algebra and a semigroup to exhibit \\texttt{NP}-hardness for the membership problem of finite algebras in finitely generated varieties.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2015-12-10T02:31:37.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "68Q17",
      "20M07",
      "03C05",
      "08B99",
      "08C15"
    ],
    "keywords": [
      "flexible constraint satisfiability",
      "semigroup theory",
      "variety membership problem",
      "finite algebras",
      "universal horn class membership"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2015arXiv151203127J"
    }
  }
}