Some necessary and some sufficient conditions about the 3-satisfyability problem
MATHEMATICS AND EDUCATION IN MATHEMATICS, Sofia, 2000, pp 233-240, (Proceedings of the Twenty-Ninth Spring Conference of the Union of Bulgarian Mathematicians, Lovetch, April 3–6, 2000). http://www.math.bas.bg/smb/PK/29-2000.pdf
The so-called 3-Satisfiability problem takes an important place in the theory of NP-completeness of problems and algorithms. This work is a continuation of a previous one, where conjunctive normal forms of the zero function namely forms, such that any disjunct of which has no more than three literals (3-CNForms) have been considered and classified.
Here we shall deduce some necessary and some sufficient conditions which determine whether given sets of 3-CNForms are or are not forms of the zero function. These conditions are polynomial-time verifiable.
Some estimations of the number of these forms are also given.
3-SAT, NP-completeness, zero function, necessary conditions, sufficient conditions, conjunctive normal forms classification
Природни науки, математика и информатика
Natural sciences, mathematics and informatics