论文标题
平衡不完整的块设计和确切的满意度
Balanced incomplete block designs and exact satisfiability
论文作者
论文摘要
本文通过使用布尔公式的子句和带有布尔变量的块来识别块设计的点，探索平衡不完整的块设计（BIBD）和某些线性CNF公式之间的对应关系。 BIBDS中的平行类对应于相应公式中的XSAT解决方案。这种对应关系允许将结果从一个字段转移到另一个字段。作为一个新的结果，我们从已知的满意度定理中得出，在部分平衡的不完整块设计中找到并行类的问题是NP完整的。
The paper explores the correspondence between balanced incomplete block designs (BIBD) and certain linear CNF formulas by identifying the points of a block design with the clauses of the Boolean formula and blocks with Boolean variables. Parallel classes in BIBDs correspond to XSAT solutions in the corresponding formula. This correspondence allows for transfers of results from one field to the other. As a new result we deduce from known satisfiability theorems that the problem of finding a parallel class in a partially balanced incomplete block design is NP-complete.
