加载中…
The satisfiability problem is NP-complete but there are subclasses where all the instances are satisfiable. For this, restrictions on the shape of the formula are made. Darman and Döcker show that the subclass MONOTONE -SAT-(,1) with proves to be NP-complete and pose the open question whether instances of MONOTONE -SAT-(3,1) are satisfiable. This paper shows that all instances of MONOTONE -SAT-(3,1) are satisfiable using the new concept of a color-structures.

生成讲解博客的中文版本

生成AI智能校验的中文版本