Answers are grounded in this paper and cite their sources.
In 2004 Atserias, Kolaitis, and Vardi proposed OBDD -based propositional proof systems that prove unsatisfiability of a CNF formula by deduction of an identically false OBDD from OBDD s representing clauses of the initial formula. All OBDD s in such proofs have the same order of variables. We initiate the study of OBDD based proof systems that additionally contain a rule that allows changing the order in OBDD s. At first we consider a proof system OBDD( , reordering) that uses the conjunction (join) rule and the rule that allows changing the order. We exponentially separate this proof system from OBDD( ) proof system that uses only the conjunction rule. We prove exponential lower bounds on the size of OBDD( , reordering) refutations of Tseitin formulas and the pigeonhole principle. The first lower bound was previously unknown even for OBDD( ) proofs and the second one extends the result of Tveretina et al. from OBDD( ) to OBDD( , reordering) . In 2001 Aguirre and Vardi proposed an approach to the propositional satisfiability problem based on OBDD s and symbolic quantifier elimination (we denote algorithms based on this approach as OBDD( , ∃ ) algorithms). We augment these algorithms with the operation of reordering of variables and call the new scheme OBDD( , ∃ , reordering) algorithms. We notice that there exists an OBDD( , ∃ ) algorithm that solves satisfiable and unsatisfiable Tseitin formulas in polynomial time (a standard example of a hard system of linear equations over F₂ ), but we show that there are formulas representing systems of linear equations over F₂ that are hard for OBDD( , ∃ , reordering) algorithms. Our hard instances are satisfiable formulas representing systems of linear equations over F₂ that correspond to checksum matrices of error correcting codes.
No takes yet. Share an insight, caveat, or question.
Itsykson et al. (2020) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: