DOI

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 авг 20171 сен 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/171/09/17

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

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

ID: 49785398