Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms

Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert

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

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

Аннотация

We give a deterministic algorithm for testing satisfiability of Boolean formulas in conjunctive normal form with no restriction on clause length. Its upper bound on the worst-case running time matches the best known upper bound for randomized satisfiability-testing algorithms [6]. In comparison with the randomized algorithm in [6], our deterministic algorithm is simpler and more intuitive.

Язык оригиналаанглийский
Название основной публикацииAlgorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings
ИздательSpringer Nature
Страницы60-68
Число страниц9
ISBN (печатное издание)354034375X, 9783540343752
DOI
СостояниеОпубликовано - 1 янв 2006
Событие6th Italian Conference on Algorithms and Complexity, CIAC 2006 - Rome, Италия
Продолжительность: 29 мая 200631 мая 2006

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

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

Конференция

Конференция6th Italian Conference on Algorithms and Complexity, CIAC 2006
СтранаИталия
ГородRome
Период29/05/0631/05/06

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

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

Fingerprint Подробные сведения о темах исследования «Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms». Вместе они формируют уникальный семантический отпечаток (fingerprint).

  • Цитировать

    Dantsin, E., Hirsch, E. A., & Wolpert, A. (2006). Clause shortening combined with pruning yields a new upper bound for deterministic SAT algorithms. В Algorithms and Complexity - 6th Italian Conference, CIAC 2006, Proceedings (стр. 60-68). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 3998 LNCS). Springer Nature. https://doi.org/10.1007/11758471_9