Deterministic algorithms for k-SAT based on covering codes and local search

Evgeny Dantsin, Andreas Goerdt, Edward A. Hirsch, Uwe Schöning

Результат исследований: Публикации в книгах, отчётах, сборниках, трудах конференцийстатья в сборнике материалов конференциинаучнаярецензирование

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

Аннотация

We show that satisfiability of formulas in k-CNF can be decided deterministically in time close to (2k/(k + 1))n, where n is the number of variables in the input formula. This is the best known worst-case upper bound for deterministic k-SAT algorithms. Our algorithm can be viewed as a derandomized version of Schöning’s probabilistic algorithm presented in [15]. The key point of our algorithm is the use of covering codes together with local search. Compared to other “weakly exponential” algorithms, our algorithm is technically quite simple. We also show how to improve the bound above by moderate technical effort. For 3-SAT the improved bound is 1.481n.

Язык оригиналаанглийский
Название основной публикацииAutomata, Languages and Programming - 27th International Colloquium, ICALP 2000, Proceedings
РедакторыUgo Montanari, Emo Welzl, Jose D. P. Rolim
ИздательSpringer Nature
Страницы236-247
Число страниц12
ISBN (печатное издание)9783540450221
СостояниеОпубликовано - 1 янв 2000
Событие27th International Colloquium on Automata, Languages and Programming, ICALP 2000 - Geneva, Швейцария
Продолжительность: 9 июл 200015 июл 2000

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том1853
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция27th International Colloquium on Automata, Languages and Programming, ICALP 2000
Страна/TерриторияШвейцария
ГородGeneva
Период9/07/0015/07/00

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

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

Fingerprint

Подробные сведения о темах исследования «Deterministic algorithms for k-SAT based on covering codes and local search». Вместе они формируют уникальный семантический отпечаток (fingerprint).

Цитировать