Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-16T12:18:47.028Z Has data issue: false hasContentIssue false

ON OBDD-BASED ALGORITHMS AND PROOF SYSTEMS THAT DYNAMICALLY CHANGE THE ORDER OF VARIABLES

Published online by Cambridge University Press:  22 June 2020

DMITRY ITSYKSON
Affiliation:
ST. PETERSBURG DEPARTMENT OF V.A. STEKLOV INSTITUTE OF MATHEMATICS RUSSIAN ACADEMY OF SCIENCE ST. PETERSBURG, RUSSIA E-mail: dmitrits@pdmi.ras.ru
ALEXANDER KNOP
Affiliation:
ST. PETERSBURG DEPARTMENT OF V.A. STEKLOV INSTITUTE OF MATHEMATICS RUSSIAN ACADEMY OF SCIENCE ST. PETERSBURG, RUSSIA E-mail: aknop@ucsd.edu
ANDREI ROMASHCHENKO
Affiliation:
LIRMM UNIV MONTPELLIER, CNRS MONTPELLIER, FRANCE and ON LEAVE FROM IITP RAS MOSCOW, RUSSIA E-mail: andrei.romashchenko@lirmm.fr
DMITRY SOKOLOV
Affiliation:
ST. PETERSBURG DEPARTMENT OF V.A. STEKLOV INSTITUTE OF MATHEMATICS RUSSIAN ACADEMY OF SCIENCE ST. PETERSBURG, RUSSIA E-mail: sokolov.dmt@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

In 2004 Atserias, Kolaitis, and Vardi proposed $\text {OBDD}$-based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of an identically false $\text {OBDD}$ from $\text {OBDD}$s representing clauses of the initial formula. All $\text {OBDD}$s in such proofs have the same order of variables. We initiate the study of $\text {OBDD}$ based proof systems that additionally contain a rule that allows changing the order in $\text {OBDD}$s. At first we consider a proof system $\text {OBDD}(\land , \text{reordering})$ that uses the conjunction (join) rule and the rule that allows changing the order. We exponentially separate this proof system from $\text {OBDD}(\land )$ proof system that uses only the conjunction rule. We prove exponential lower bounds on the size of $\text {OBDD}(\land , \text{reordering})$ refutations of Tseitin formulas and the pigeonhole principle. The first lower bound was previously unknown even for $\text {OBDD}(\land )$ proofs and the second one extends the result of Tveretina et al. from $\text {OBDD}(\land )$ to $\text {OBDD}(\land , \text{reordering})$.

In 2001 Aguirre and Vardi proposed an approach to the propositional satisfiability problem based on $\text {OBDD}$s and symbolic quantifier elimination (we denote algorithms based on this approach as $\text {OBDD}(\land , \exists )$ algorithms). We augment these algorithms with the operation of reordering of variables and call the new scheme $\text {OBDD}(\land , \exists , \text{reordering})$ algorithms. We notice that there exists an $\text {OBDD}(\land , \exists )$ algorithm that solves satisfiable and unsatisfiable Tseitin formulas in polynomial time (a standard example of a hard system of linear equations over $\mathbb {F}_2$), but we show that there are formulas representing systems of linear equations over $\mathbb {F}_2$ that are hard for $\text {OBDD}(\land , \exists , \text{reordering})$ algorithms. Our hard instances are satisfiable formulas representing systems of linear equations over $\mathbb {F}_2$ that correspond to checksum matrices of error correcting codes.

MSC classification

Information

Type
Articles
Copyright
© The Association for Symbolic Logic 2020