[PS][PS] Propositional proof complexity: Past, present and future
P Beame, T Pitassi - Bulletin of the EATCS, 1998 - homes.cs.washington.edu
Proof complexity, the study of the lengths of proofs in propositional logic, is an area of study
that is fundamentally connected both to major open questions of computational complexity …
that is fundamentally connected both to major open questions of computational complexity …
[PDF][PDF] Automatic SAT-compilation of planning problems
Recent work by Kautz et al. provides tantalizing evidence that large, classical planning
problems may be e ciently solved by translating them into propositional satis ability …
problems may be e ciently solved by translating them into propositional satis ability …
[PDF][PDF] Computational challenges in propositional reasoning and search
The past several years have seen much progress in the area of propositional reasoning and
satis ability testing. There is a growing consensus by researchers on the key technical …
satis ability testing. There is a growing consensus by researchers on the key technical …
Partition-based logical reasoning for first-order and propositional theories
E Amir, S McIlraith - Artificial intelligence, 2005 - Elsevier
In this paper we show how tree decomposition can be applied to reasoning with first-order
and propositional logic theories. Our motivation is two-fold. First, we are concerned with how …
and propositional logic theories. Our motivation is two-fold. First, we are concerned with how …
Pushing the limits of rule reasoning in transformers through natural language satisfiability
K Richardson, A Sabharwal - Proceedings of the AAAI Conference on …, 2022 - ojs.aaai.org
Investigating the reasoning abilities of transformer models, and discovering new challenging
tasks for them, has been a topic of much interest. Recent studies have found these models to …
tasks for them, has been a topic of much interest. Recent studies have found these models to …
[PDF][PDF] The LPSAT engine & its application to resource planning
SA Wolfman, DS Weld - IJCAI, 1999 - Citeseer
Compilation to boolean satisfiability has become a powerful paradigm for solving AI
problems. However, domains that require metric reasoning cannot be compiled efficiently to …
problems. However, domains that require metric reasoning cannot be compiled efficiently to …
Solving difficult SAT instances in the presence of symmetry
Research in algorithms for Boolean satisfiability and their implementations [23, 6] has
recently outpaced benchmarking efforts. Most of the classic DIMACS benchmarks [10] can …
recently outpaced benchmarking efforts. Most of the classic DIMACS benchmarks [10] can …
Incremental SAT-based reverse engineering of camouflaged logic circuits
Layout-level gate or routing camouflaging techniques have attracted interest as
countermeasures against reverse engineering of combinational logic. In order to minimize …
countermeasures against reverse engineering of combinational logic. In order to minimize …
Solving difficult instances of boolean satisfiability in the presence of symmetry
Research in algorithms for Boolean satisfiability (SAT) and their implementations (Goldberg
and Novikov, 2002),(Moskewicz et al., 2001),(Silva and Sakallah, 1999) has recently …
and Novikov, 2002),(Moskewicz et al., 2001),(Silva and Sakallah, 1999) has recently …
Backbone fragility and the local search cost peak
The local search algorithm WSat is one of the most successful algorithms for solving the
satisfiability (SAT) problem. It is notably effective at solving hard Random 3-SAT instances …
satisfiability (SAT) problem. It is notably effective at solving hard Random 3-SAT instances …