Answers are grounded in this paper and cite their sources.
Resolution over linear equations is a natural extension of the popular resolution refutation system, augmented with the ability to carry out basic counting. Denoted Res( linR) , this refutation system operates with disjunctions of linear equations with Boolean variables over a ring R, to refute unsatisfiable sets of such disjunctions. Beginning in the work of Raz & Tzameret (2008), through the work of Itsykson & Sokolov (2020) which focused on tree-like lower bounds, this refutation system was shown to be fairly strong. Subsequent work (cf. Garlik & Kołodziejczyk 2018; Itsykson & Sokolov 2020; Krajícek 2017; Krajícek & Oliveira 2018) made it evident that establishing lower bounds against general Res( linR) refutations is a challenging and interesting task since the system captures a ``minimal'' extension of resolution with counting gates for which no super-polynomial lower bounds are known to date. We provide the first super-polynomial size lower bounds against general (dag-like) resolution over linear equations refutations in the large characteristic regime. In particular, we prove that the subset-sum principle 1+∑ᵢ₌₁ⁿ2ⁱ xᵢ = 0 requires refutations of exponential size over Q . We use a novel lower bound technique: We show that under certain conditions every refutation of a subset-sum instance $$f=0$$ must pass through a fat clause consisting of the equation f=α for every α in the image of f under Boolean assignments, or can be efficiently reduced to a proof containing such a clause. We then modify this approach to prove exponential lower bounds against tree-like refutations of any subset-sum instance that depends on n variables, hence also separating tree-like from dag-like refutations over the rationals. We then turn to the finite fields regime, showing that the work of Itsykson & Sokolov (2020), where tree-like lower bounds over F₂ were obtained, can be carried over and extended to every finite field. We establish new lower bounds and separations as follows: (i) For every pair of distinct primes $$p,q$$ , there exist CNF formulas with short tree-like refutations in Res( linFₚ) that require exponential-size tree-like Res( linFq) refutations; (ii) random k-CNF formulas require exponential-size tree-like Res( linFₚ) refutations, for every prime p and constant k; and (iii) exponential-size lower bounds for tree-like Res( linF) refutations of the pigeonhole principle, for every field F .
No takes yet. Share an insight, caveat, or question.
Part et al. (2021) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: