TY - ELEC
AU - Knop, Alexander
PY - 2018
TI - Hard Satisfiable Formulas for Splittings by Linear Combinations
LA - eng
M3 - Moving Image
AB - Itsykson and Sokolov in 2014 introduced the class of DPLL(xor) 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(xor) 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(xor) algorithms on unsatisfiable
formulas. In the talk, we discuss several subclasses of DPLL(xor)
algorithms and explain lower bounds for one of them.
N2 - Itsykson and Sokolov in 2014 introduced the class of DPLL(xor) 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(xor) 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(xor) algorithms on unsatisfiable
formulas. In the talk, we discuss several subclasses of DPLL(xor)
algorithms and explain lower bounds for one of them.
UR - https://open.library.ubc.ca/collections/48630/items/1.0377822
ER - End of Reference