Embedding Ordered Sets into Distributive Lattices

详细信息    查看全文

• 作者：C. J. Van Alten
• 关键词：Ordered set ; Distributive lattice ; NP ; complete
• 刊名：Order
• 出版年：2016
• 出版时间：November 2016
• 年：2016
• 卷：33
• 期：3
• 页码：419-427
• 全文大小：363 KB
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Convex and Discrete Geometry
  Geometry
  Theory of Computation
  
• 出版者：Springer Netherlands
• ISSN：1572-9273
• 卷排序：33

文摘

This paper investigates the class of ordered sets that are embeddable into a distributive lattice in such a way that all existing finite meets and joins are preserved. The main result is that the following decision problem is NP-complete: Given a finite ordered set, is it embeddable into a distributive lattice with preservation of existing meets and joins? The NP-hardness of the problem is proved by polynomial reduction of the classical 3SAT decision problem into it, and the NP-completeness by presenting a suitable NP-algorithm.