Skip to main content

SATISFACTIBILIDAD Y OPTIMIZACION CON CERTIFICADOS DE PRUEBA MAS ALLA DE RESOLUCION - APLICACIONES (PROOFS BEYOND-A)

PID2022-138506NB-C21

•
Funding agency name Agencia Estatal de Investigación
Funding agency acronym AEI
Program Programa Estatal para Impulsar la Investigación Científico-Técnica y su Transferencia
Subprogram Subprograma Estatal de Generación de Conocimiento
Call Proyectos de I+D+i (Generación de Conocimiento y Retos Investigación)
Call year 2022
State Plan 2021-2023 Plan Estatal de Investigación Científica y Técnica y de Innovación
Beneficiary centre UNIVERSIDAD DE LLEIDA

Resultados relacionados

Resultados totales (Incluyendo duplicados): 10
Encontrada(s) 1 página(s)

Repositori Obert UdL
Publication Contribución de congreso (ConferenceOutput)

On the Density of States of Boolean Formulas

  • Ansótegui Gil, Carlos José
  • Bonet, Maria Luisa
  • Levy, Jordi
Given a CNF formula with m clauses, and an integer k, where 0 ≤ k ≤ m, a density of states procedure will count the number of truth assignments that falsify exactly k clauses of the formula. We present the first approach to compute the density of states of Boolean formulas exactly. This is the first non-trivial result on this known hard problem. There are previous approaches for computing approximately the density of states of Boolean Formulas [1,2], where the authors point out they are not aware of any complete solver that is able to compute the exact density of states. The present work is the first step to fill this gap. The idea is, given a formula φ and a parameter c, construct a formula φc such that, the number of models of φc is the number of assignments that falsify exactly c clauses of φ. Then, a #SAT solver is used as a black box to count the models of φc. This approach can be also used to compute approximately the density of states by using an approximate #SAT solver. Finally, the method can be extended trivially to deal with Weighted Boolean formulas., This research is part of the projects PROOFS (PID2019-109137GB-C21) and PROOFS BEYOND (PID2022-138506NB-C21) funded by the AEI and MCIN
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

Revisiting SAT-based Solvers: MaxSAT Rules and Core Sequences

  • Alòs, Josep
  • Ansótegui Gil, Carlos José
  • Torres Montiel, Eduard
In this paper, we revisit the state-of-the-art of MaxSAT solving. We focus on SAT-based MaxSAT solving algorithms, mainly on Core-guided MaxSAT solvers. We show how to describe Core-guided solvers with Non-CNF MaxSAT rules plus the Extension rule. Equipped with these rules, we show how to apply them alternatively to obtain new Core-guided MaxSAT solvers. Since Core-guided solvers essentially solve a sequence of SAT instances, we also discuss how Core-guided MaxSAT solvers traverse the search space of possible sequences of SAT instances, the existence of exponentially harder sequences, and how to avoid them. The experimental investigation shows comparable and complementary performance to state-of-the-art solvers., This work was supported by the project PROOFS BEYOND (grant number PID2022-138506NB-C21) funded by the AEI.
Repositori Obert UdL
Publication Artículo científico (JournalArticle)

SAT, gadgets, Max2XOR, and quantum annealers

  • Ansótegui Gil, Carlos José
  • Levy, Jordi
Quantum annealers are presented as quantum computers that can, with a high probability, optimize certain quadratic functions on Boolean variables in constant time. These functions are basically the Hamiltonian of Ising models that reach the ground energy state with a high probability after an annealing process. In some preliminary works, they have been proposed as a way to solve SAT. These Hamiltonians can be seen as Max2XOR problems, i.e., as the problem of finding an assignment that maximizes the number of XOR clauses of at most two variables that are satisfied. In this paper, we focus on introducing several gadgets to reduce SAT to Max2XOR. We show how they can be used to translate SAT instances to initial configurations of a quantum annealer., This work was supported by the project PROOFS BEYOND (grant number PID2022-138506NB-C21) funded by the AEI.
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publication Artículo científico (JournalArticle)

Polynomial calculus for optimization

  • Bonacina, Ilario
  • Bonet, María Luisa
  • Levy, Jordi
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
DIGITAL.CSIC. Repositorio Institucional del CSIC
Publication Artículo científico (JournalArticle)

SAT, gadgets, Max2XOR, and quantum annealers

  • Ansótegui, Carlos
  • Levy, Jordi
Quantum annealers are presented as quantum computers that can, with a high probability, optimize certain quadratic functions on Boolean variables in constant time. These functions are basically the Hamiltonian of Ising models that reach the ground energy state with a high probability after an annealing process. In some preliminary works, they have been proposed as a way to solve SAT. These Hamiltonians can be seen as Max2XOR problems, i.e., as the problem of finding an assignment that maximizes the number of XOR clauses of at most two variables that are satisfied. In this paper, we focus on introducing several gadgets to reduce SAT to Max2XOR. We show how they can be used to translate SAT instances to initial configurations of a quantum annealer., This work was supported by the project PROOFS BEYOND (grant number PID2022-138506NB-C21) funded by the AEI., Peer reviewed
UPCommons. Portal del coneixement obert de la UPC
Publication Contribución de congreso (ConferenceOutput)

Redundancy rules for MaxSAT

  • Bonacina, Ilario|||0000-0002-5697-8070
  • Bonet Carbonell, M. Luisa|||0000-0003-1646-7177
  • Buss, Sam
  • Lauria, Massimo
The concept of redundancy in SAT leads to more expressive and powerful proof search techniques, e.g., able to express various inprocessing techniques, and originates interesting hierarchies of proof systems [Heule et.al'20, Buss-Thapen'19]. Redundancy has also been integrated in MaxSAT [Ihalainen et.al'22, Berg et.al'23, Bonacina et.al'24]. In this paper, we define a structured hierarchy of redundancy proof systems for MaxSAT, with the goal of studying its proof complexity. We obtain MaxSAT variants of proof systems such as SPR, PR, SR, and others, previously defined for SAT. All our rules are polynomially checkable, unlike [Ihalainen et.al'22]. Moreover, they are simpler and weaker than [Berg et.al'23], and possibly amenable to lower bounds. This work also complements the approach of [Bonacina et.al'24]. Their proof systems use different rule sets for soft and hard clauses, while here we propose a system using only hard clauses and blocking variables. This is easier to integrate with current solvers and proof checkers. We discuss the strength of the systems introduced, we show some limitations of them, and we give a short cost-SR proof that any assignment for the weak pigeonhole principle PHP^m_n falsifies at least m-n clauses., Ilario Bonacina: The author was supported by grant PID2022-138506NB-C22 (PROOFS BEYOND) funded by AEI. Maria Luisa Bonet: The author was supported by grant PID2022-138506NB-C21 (PROOFS BEYOND) funded by AEI. Massimo Lauria: The author has been supported by the project PRIN 2022 “Logical Methods in Combinatorics” N. 2022BXH4R5 of the Italian Ministry of University and Research (MIUR)., Peer Reviewed
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

SAT, gadgets, Max2XOR, and quantum annealers

  • Ansótegui Gil, Carlos José
  • Levy, Jordi
Quantum annealers are presented as quantum computers that can, with a high probability, optimize certain quadratic functions on Boolean variables in constant time. These functions are basically the Hamiltonian of Ising models that reach the ground energy state with a high probability after an annealing process. In some preliminary works, they have been proposed as a way to solve SAT. These Hamiltonians can be seen as Max2XOR problems, i.e., as the problem of finding an assignment that maximizes the number of XOR clauses of at most two variables that are satisfied. In this paper, we focus on introducing several gadgets to reduce SAT to Max2XOR. We show how they can be used to translate SAT instances to initial configurations of a quantum annealer., This work was supported by the project PROOFS BEYOND (grant number PID2022-138506NB-C21) funded by the AEI.
Recercat. Dipósit de la Recerca de Catalunya
Publication Artículo científico (JournalArticle)

Revisiting SAT-based Solvers: MaxSAT Rules and Core Sequences

  • Alòs, Josep
  • Ansótegui Gil, Carlos José
  • Torres Montiel, Eduard
In this paper, we revisit the state-of-the-art of MaxSAT solving. We focus on SAT-based MaxSAT solving algorithms, mainly on Core-guided MaxSAT solvers. We show how to describe Core-guided solvers with Non-CNF MaxSAT rules plus the Extension rule. Equipped with these rules, we show how to apply them alternatively to obtain new Core-guided MaxSAT solvers. Since Core-guided solvers essentially solve a sequence of SAT instances, we also discuss how Core-guided MaxSAT solvers traverse the search space of possible sequences of SAT instances, the existence of exponentially harder sequences, and how to avoid them. The experimental investigation shows comparable and complementary performance to state-of-the-art solvers., This work was supported by the project PROOFS BEYOND (grant number PID2022-138506NB-C21) funded by the AEI.
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

Redundancy rules for MaxSAT

  • Bonacina, Ilario
  • Bonet Carbonell, M. Luisa
  • Buss, Sam
  • Lauria, Massimo
The concept of redundancy in SAT leads to more expressive and powerful proof search techniques, e.g., able to express various inprocessing techniques, and originates interesting hierarchies of proof systems [Heule et.al'20, Buss-Thapen'19]. Redundancy has also been integrated in MaxSAT [Ihalainen et.al'22, Berg et.al'23, Bonacina et.al'24]. In this paper, we define a structured hierarchy of redundancy proof systems for MaxSAT, with the goal of studying its proof complexity. We obtain MaxSAT variants of proof systems such as SPR, PR, SR, and others, previously defined for SAT. All our rules are polynomially checkable, unlike [Ihalainen et.al'22]. Moreover, they are simpler and weaker than [Berg et.al'23], and possibly amenable to lower bounds. This work also complements the approach of [Bonacina et.al'24]. Their proof systems use different rule sets for soft and hard clauses, while here we propose a system using only hard clauses and blocking variables. This is easier to integrate with current solvers and proof checkers. We discuss the strength of the systems introduced, we show some limitations of them, and we give a short cost-SR proof that any assignment for the weak pigeonhole principle PHP^m_n falsifies at least m-n clauses., Ilario Bonacina: The author was supported by grant PID2022-138506NB-C22 (PROOFS BEYOND) funded by AEI. Maria Luisa Bonet: The author was supported by grant PID2022-138506NB-C21 (PROOFS BEYOND) funded by AEI. Massimo Lauria: The author has been supported by the project PRIN 2022 “Logical Methods in Combinatorics” N. 2022BXH4R5 of the Italian Ministry of University and Research (MIUR)., Peer Reviewed, Postprint (published version)
Recercat. Dipósit de la Recerca de Catalunya
Publication Contribución de congreso (ConferenceOutput)

On the Density of States of Boolean Formulas

  • Ansótegui Gil, Carlos José
  • Bonet, Maria Luisa
  • Levy, Jordi
Given a CNF formula with m clauses, and an integer k, where 0 ≤ k ≤ m, a density of states procedure will count the number of truth assignments that falsify exactly k clauses of the formula. We present the first approach to compute the density of states of Boolean formulas exactly. This is the first non-trivial result on this known hard problem. There are previous approaches for computing approximately the density of states of Boolean Formulas [1,2], where the authors point out they are not aware of any complete solver that is able to compute the exact density of states. The present work is the first step to fill this gap. The idea is, given a formula φ and a parameter c, construct a formula φc such that, the number of models of φc is the number of assignments that falsify exactly c clauses of φ. Then, a #SAT solver is used as a black box to count the models of φc. This approach can be also used to compute approximately the density of states by using an approximate #SAT solver. Finally, the method can be extended trivially to deal with Weighted Boolean formulas., This research is part of the projects PROOFS (PID2019-109137GB-C21) and PROOFS BEYOND (PID2022-138506NB-C21) funded by the AEI and MCIN