6 found
  1.  1
    SAT-based MaxSAT algorithms.Carlos Ansótegui, Maria Luisa Bonet & Jordi Levy - 2013 - Artificial Intelligence 196 (C):77-105.
  2. Resolution for Max-SAT.María Luisa Bonet, Jordi Levy & Felip Manyà - 2007 - Artificial Intelligence 171 (8-9):606-618.
  3.  62
    The deduction rule and linear and near-linear proof simulations.Maria Luisa Bonet & Samuel R. Buss - 1993 - Journal of Symbolic Logic 58 (2):688-709.
    We introduce new proof systems for propositional logic, simple deduction Frege systems, general deduction Frege systems, and nested deduction Frege systems, which augment Frege systems with variants of the deduction rule. We give upper bounds on the lengths of proofs in Frege proof systems compared to lengths in these new systems. As applications we give near-linear simulations of the propositional Gentzen sequent calculus and the natural deduction calculus by Frege proofs. The length of a proof is the number of lines (...)
    Direct download (8 more)  
    Export citation  
    Bookmark   4 citations  
  4.  35
    Degree complexity for a modified pigeonhole principle.Maria Luisa Bonet & Nicola Galesi - 2003 - Archive for Mathematical Logic 42 (5):403-414.
    . We consider a modification of the pigeonhole principle, M P H P, introduced by Goerdt in [7]. M P H P is defined over n pigeons and log n holes, and more than one pigeon can go into a hole. Using a technique of Razborov [9] and simplified by Impagliazzo, Pudlák and Sgall [8], we prove that any Polynomial Calculus refutation of a set of polynomials encoding the M P H P, requires degree Ω. We also prove a simple (...)
    No categories
    Direct download (4 more)  
    Export citation  
  5.  21
    Quasipolynomial size Frege proofs of frankl’s theorem on the trace of sets.James Aisenberg, Maria Luisa Bonet & Sam Buss - 2016 - Journal of Symbolic Logic 81 (2):687-710.
    We extend results of Bonet, Buss and Pitassi on Bondy’s Theorem and of Nozaki, Arai and Arai on Bollobás’ Theorem by proving that Frankl’s Theorem on the trace of sets has quasipolynomial size Frege proofs. For constant values of the parametert, we prove that Frankl’s Theorem has polynomial size AC0-Frege proofs from instances of the pigeonhole principle.
    Direct download (5 more)  
    Export citation  
  6.  2
    Propositional proof systems based on maximum satisfiability.Maria Luisa Bonet, Sam Buss, Alexey Ignatiev, Antonio Morgado & Joao Marques-Silva - 2021 - Artificial Intelligence 300 (C):103552.
    Direct download (2 more)  
    Export citation