A deterministic (2 - 2/(k + 1))n algorithm for k-SAT based on local search

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Ravi Kannan, Jon Kleinberg, Christos Papadimitriou, Prabhakar Raghavan, Uwe Schöning

Результат исследований: Научные публикации в периодических изданияхстатьярецензирование

129 Цитирования (Scopus)

Аннотация

Local search is widely used for solving the propositional satisfiability problem. Papadimitriou (1991) showed that randomized local search solves 2-SAT in polynomial time. Recently, Schöning (1999) proved that a close algorithm for k-SAT takes time (2 - 2/k)n up to a polynomial factor. This is the best known worst-case upper bound for randomized 3-SAT algorithms (cf. also recent preprint by Schuler et al.). We describe a deterministic local search algorithm for k-SAT running in time (2 - 2/(k + 1))n up to a polynomial factor. The key point of our algorithm is the use of covering codes instead of random choice of initial assignments. Compared to other "weakly exponential" algorithms, our algorithm is technically quite simple. We also describe an improved version of local search. For 3-SAT the improved algorithm runs in time 1.481n up to a polynomial factor. Our bounds are better than all previous bounds for deterministic k-SAT algorithms.

Язык оригиналаанглийский
Страницы (с-по)69-83
Число страниц15
ЖурналTheoretical Computer Science
Том289
Номер выпуска1
DOI
СостояниеОпубликовано - 23 окт 2002

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

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

Fingerprint

Подробные сведения о темах исследования «A deterministic (2 - 2/(k + 1))<sup>n</sup> algorithm for k-SAT based on local search». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать