This repository contains some notes about a problem involving coverings of coatoms in partition lattices, which we prove is NP-complete.
Title: [Filter membership of coatoms in a partition lattice is NP-complete] (https://github.com/TypeFunc/lat-nae-3sat/raw/master/article/lat-nae-3sat.pdf)
Authors: William DeMeo @williamdemeo and Hyeyoung Shin @hyeyoungshin
Journal: (not yet published)
Year: 2016
Abstract: We show that 3-SAT reduces to the problem of deciding whether all coatoms in a certain partition lattice are contained in the union of a collection of certain principal filters of the lattice, so the latter problem is NP-complete. We conclude with a discussion of the tractability of such filter membership problems.
BibTeX entry:
@unpublished {DeMeoShin:2016,
AUTHOR = {DeMeo, William and Shin, Hyeyoung},
TITLE = {Filter membership of coatoms in a partition lattice is NP-complete},
YEAR = {2016},
URL = {https://github.com/TypeFunc/lat-nae-3sat/}
}
For questions, comments, or suggestions please submit an issue.
Thanks for your interest in this work!