DOI

The exact 3-satisfiability problem (X3SAT) is formulated as follows: given a Boolean formula in 3-CNF, find a truth assignment such that exactly one literal in each clause is set to true. It is well known that X3SAT is NP-complete. In this paper, we present an exact algorithm solving X3SAT in time O(20.162536n), where n is the number of variables. Our proof of this bound is slightly simpler than that of Porschen, Randerath, and Speckenmeyer. These proofs are independent (and algorithms are slightly different), though they are based on the same ideas appeared in the proof of the previous bound O(20.186916n) by the same authors. Bibliography: 6 titles.

Язык оригиналаанглийский
Страницы (с-по)1195-1199
Число страниц5
ЖурналJournal of Mathematical Sciences
Том126
Номер выпуска3
DOI
СостояниеОпубликовано - 1 янв 2005

    Предметные области Scopus

  • Теория вероятности и статистика
  • Математика (все)
  • Прикладная математика

ID: 49824495