DOI

It is still not known whether the satisfiability problem (SAT), and hence the maximum satisdiability problem (MAX-SAT), can be solved in time poly({pipe}F{pipe})cn for c < 2, where c is a constant, n is the number of variables, and F is the input formula. However, such bounds are known for some special cases of these problems where the clause length, the maximum number of variable occurrences, or the length of the formula is bounded. In this paper, we consider the (n, 3)-MAX-SAT problem-the special case of MAX-SAT where each variable appears in a formula at most three times. We present a simple algorithm with running time O*(2n/3). As a byproduct, we also obtain a polynomially sovable subclass that may be of independent interest. Bibliography: 13 titles.

Язык оригиналаанглийский
Страницы (с-по)1-6
Число страниц6
ЖурналJournal of Mathematical Sciences (United States)
Том188
Номер выпуска1
DOI
СостояниеОпубликовано - 1 янв 2013

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

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

ID: 49788084