Computer users encounter configuration on daily basis. Whether when they customize an
application they use, customize how a new application is installed, or just customize a query …

The past decade has seen clause learning as the most successful algorithm for SAT
instances arising from real-world applications. This practical success is accompanied by …

We introduce a more general notion of efficient simulation between proof systems, which we
call effectively-p simulation. We argue that this notion is more natural from a complexity …

Groote and Zantema proved that a particular OBDD computation of the pigeonhole formula
has exponential size, and that limited OBDD derivations cannot simulate resolution …

We consider extensions of the DPLL approach to satisfiability testing that add a version of
memoization, in which formulas that the algorithm has previously shown to be unsatisfiable …

Proof complexity is an interdisciplinary area of research utilising techniques from logic,
complexity, and combinatorics towards the main aim of understanding the complexity of …

For current state-of-the-art DPLL SAT-solvers the two main bottlenecks are the amounts of
time and memory used. In proof complexity, these resources correspond to the length and …

Unless we resolve the P vs NP question, we are unable to say whether there is an algorithm
(acceptor) that accepts Boolean tautologies in polynomial time and does not accept non …

Cook and Krajíček have recently obtained the following Karp-Lipton collapse result in
bounded arithmetic: if the theory PV proves NP⊆ P/poly, then the polynomial hierarchy …

We prove that TAUT has ap-optimal proof system if and only if a logic related to least fixed-
point logic captures polynomial time on all finite structures. Furthermore, we show that TAUT …