Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR17-117 | 20th July 2017 22:23

Hard satisfiable formulas for splittings by linear combinations


Authors: Dmitry Itsykson, Alexander Knop
Publication: 23rd July 2017 00:08
Downloads: 74


Itsykson and Sokolov in 2014 introduced the class of DPLL($\oplus$) 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($\oplus$) algorithms solve in polynomial time systems of linear equations modulo two that are hard for DPLL, PPSZ and CDCL algorithms. Itsykson and Sokolov have proved first exponential lower bounds for DPLL($\oplus$) algorithms on unsatisfiable formulas.

In this paper we consider a subclass of DPLL($\oplus$) 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($\oplus$). We give a construction of a family of satisfiable CNF formulas $\Psi_n$ of size poly($n$) such that any drunken DPLL($\oplus$) algorithm with probability at least $1 - 2^{-\Omega(n)}$ runs at least $2^{\Omega(n)}$ steps on $\Psi_n$; thus we solve an open question stated in the paper of Itsykson and Sokolov. This lower bound extends the result of Alekhnovich, Hirsch and Itsykson (2005) from drunken DPLL to drunken DPLL($\oplus$).

ISSN 1433-8092 | Imprint