On proof complexity of resolution over polynomial calculus

0559957 - MÚ 2023 RIV US eng J - Článek v odborném periodiku
Khaniki, Erfan
On proof complexity of resolution over polynomial calculus.
ACM Transactions on Computational Logic. Roč. 23, č. 3 (2022), č. článku 16. ISSN 1529-3785. E-ISSN 1557-945X
Grant CEP: GA ČR(CZ) GX19-27871X
Institucionální podpora: RVO:67985840
Klíčová slova: lower bounds * modular counting * Polynomial Calculus * propositional pigeonhole principle
Obor OECD: Pure mathematics
Impakt faktor: 0.5, rok: 2022
Způsob publikování: Omezený přístup
https://doi.org/10.1145/3506702

The proof system Res (PCd,R) is a natural extension of the Resolution proof system that instead of disjunctions of literals operates with disjunctions of degree d multivariate polynomials over a ring R with Boolean variables. Proving super-polynomial lower bounds for the size of Res(PC1,R)-refutations of Conjunctive normal forms (CNFs) is one of the important problems in propositional proof complexity. The existence of such lower bounds is even open for Res(PC1,) when is a finite field, such as 2. In this article, we investigate Res(PCd,R) and tree-like Res(PCd,R) and prove size-width relations for them when R is a finite ring. As an application, we prove new lower bounds and reprove some known lower bounds for every finite field as follows:(1)We prove almost quadratic lower bounds for Res(PCd,)-refutations for every fixed d. The new lower bounds are for the following CNFs:(a)Mod q Tseitin formulas (char() q) and Flow formulas,(b)Random k-CNFs with linearly many clauses.(2)We also prove super-polynomial (more than nk for any fixed k) and also exponential (2nμ for an μ > 0) lower bounds for tree-like Res(PCd,)-refutations based on how big d is with respect to n for the following CNFs:(a)Mod q Tseitin formulas (char()q) and Flow formulas,(b)Random k-CNFs of suitable densities,(c)Pigeonhole principle and Counting mod q principle. The lower bounds for the dag-like systems are the first nontrivial lower bounds for these systems, including the case d=1. The lower bounds for the tree-like systems were known for the case d=1 (except for the Counting mod q principle, in which lower bounds for the case d> 1 were known too). Our lower bounds extend those results to the case where d> 1 and also give new proofs for the case d=1.
Trvalý link: https://hdl.handle.net/11104/0333080