Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
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(⊕).
Original language | English |
---|---|
Title of host publication | Theory and Applications of Satisfiability Testing – SAT 2017 - 20th International Conference, Proceedings |
Editors | Serge Gaspers, Toby Walsh |
Publisher | Springer Nature |
Pages | 53-61 |
Number of pages | 9 |
ISBN (Print) | 9783319662626 |
DOIs | |
State | Published - 1 Jan 2017 |
Event | 20th International Conference on Theory and Applications of Satisfiability Testing, SAT 2017 - Melbourne, Australia Duration: 28 Aug 2017 → 1 Sep 2017 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 10491 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 20th International Conference on Theory and Applications of Satisfiability Testing, SAT 2017 |
---|---|
Country/Territory | Australia |
City | Melbourne |
Period | 28/08/17 → 1/09/17 |
ID: 49785398