Skip to content

Latest commit

 

History

History
30 lines (22 loc) · 1.29 KB

README.md

File metadata and controls

30 lines (22 loc) · 1.29 KB
Raw

lat-nae-3sat

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!