Flexible constraint satisfiability and a problem in semigroup theory
Fuente:
arXiv
Gespeichert in:
| 1. Verfasser: | |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2015
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915789186007040 |
|---|---|
| author | Jackson, Marcel |
| author_facet | Jackson, Marcel |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_1512_03127 |
| institution | arXiv |
| publishDate | 2015 |
| record_format | arxiv |
| spellingShingle | Flexible constraint satisfiability and a problem in semigroup theory Jackson, Marcel Logic Computational Complexity Logic in Computer Science Combinatorics 68Q17, 20M07, 03C05, 08B99, 08C15 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. |
| title | Flexible constraint satisfiability and a problem in semigroup theory |
| topic | Logic Computational Complexity Logic in Computer Science Combinatorics 68Q17, 20M07, 03C05, 08B99, 08C15 |
| url | https://arxiv.org/abs/1512.03127 |