DIGITAL.CSIC. Repositorio Institucional del CSIC
Publication
Artículo científico (JournalArticle)
Polynomial calculus for optimization
MaxSAT is the problem of finding an assignment satisfying the maximum number of clauses in a CNF formula. We consider a natural generalization of this problem to generic sets of polynomials and propose a weighted version of Polynomial Calculus to address this problem. Weighted Polynomial Calculus is a natural generalization of the systems MaxSAT-Resolution and weighted Resolution. Unlike such systems, weighted Polynomial Calculus manipulates polynomials with coefficients in a finite field and either weights in N or Z. We show the soundness and completeness of weighted Polynomial Calculus via an algorithmic procedure. Weighted Polynomial Calculus, with weights in N and coefficients in F2, is able to prove efficiently that Tseitin formulas on a connected graph are minimally unsatisfiable. Using weights in Z, it also proves efficiently that the Pigeonhole Principle is minimally unsatisfiable., This work was supported by the grant numbers PID2019-109137GB-C21, PID2019-109137GB-C22, IJC2018-035334-I, PID2022-138506NB-C21, and PID2022-138506NB-C22 funded by AEI., Peer reviewed
Project:
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PID2019-109137GB-C21
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2022-138506NB-C21
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2021-2023 PID2022-138506NB-C22
,
AEI / Plan Estatal de Investigación Científica y Técnica y de Innovación 2017-2020 PID2019-109137GB-C22
,
AEI IJC2018-035334-I
DOI: http://hdl.handle.net/10261/378086, https://api.elsevier.com/content/abstract/scopus_id/85203000186
HANDLE: http://hdl.handle.net/10261/378086, https://api.elsevier.com/content/abstract/scopus_id/85203000186