Some necessary and some sufficient conditions about the 3-satisfyability problem


Бакоев, Валентин (2000) 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

 Издадено
  15986
 Валентин Бакоев

Научният архив поддържа инициативата за отворен достъп OAI 2.0 с начален адрес: http://da.uni-vt.bg/oai2/