We're sorry but this page doesn't work properly without JavaScript enabled. Please enable it to continue.
Feedback

Hard Satisfiable Formulas for Splittings by Linear Combinations

Formale Metadaten

Titel
Hard Satisfiable Formulas for Splittings by Linear Combinations
Serientitel
Anzahl der Teile
28
Autor
Mitwirkende
Lizenz
CC-Namensnennung - keine kommerzielle Nutzung - keine Bearbeitung 4.0 International:
Sie dürfen das Werk bzw. den Inhalt in unveränderter Form zu jedem legalen und nicht-kommerziellen Zweck nutzen, vervielfältigen, verbreiten und öffentlich zugänglich machen, sofern Sie den Namen des Autors/Rechteinhabers in der von ihm festgelegten Weise nennen.
Identifikatoren
Herausgeber
Erscheinungsjahr
Sprache

Inhaltliche Metadaten

Fachgebiet
Genre
Abstract
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.