Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Itsykson and Sokolov in 2014 introduced the class of DPLL(⊕) algorithms that solve Boolean satisfiability problem using the splitting by linear combinations of variables modulo 2. This class extends the class of DPLL algorithms that split by variables. DPLL(⊕) algorithms solve in polynomial time systems of linear equations modulo 2 that are hard for DPLL, PPSZ and CDCL algorithms. Itsykson and Sokolov have proved first exponential lower bounds for DPLL(⊕) algorithms on unsatisfiable formulas. In this paper we consider a subclass of DPLL(⊕) algorithms that arbitrary choose a linear form for splitting and randomly (with equal probabilities) choose a value to investigate first; we call such algorithms drunken DPLL(⊕). We give a construction of a family of satisfiable CNF formulas Ψn of size poly(n) such that any drunken DPLL(⊕) algorithm with probability at least 1-2-Ω(n) runs at least 2Ω(n) steps on Ψn; thus we solve an open question stated in the paper [12]. This lower bound extends the result of Alekhnovich, Hirsch and Itsykson [1] from drunken DPLL to drunken DPLL(⊕).
Язык оригинала | английский |
---|---|
Название основной публикации | Theory and Applications of Satisfiability Testing – SAT 2017 - 20th International Conference, Proceedings |
Редакторы | Serge Gaspers, Toby Walsh |
Издатель | Springer Nature |
Страницы | 53-61 |
Число страниц | 9 |
ISBN (печатное издание) | 9783319662626 |
DOI | |
Состояние | Опубликовано - 1 янв 2017 |
Событие | 20th International Conference on Theory and Applications of Satisfiability Testing, SAT 2017 - Melbourne, Австралия Продолжительность: 28 авг 2017 → 1 сен 2017 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 10491 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 20th International Conference on Theory and Applications of Satisfiability Testing, SAT 2017 |
---|---|
Страна/Tерритория | Австралия |
Город | Melbourne |
Период | 28/08/17 → 1/09/17 |
ID: 49785398