This paper describes a project that aims at showing that propositional proofs of certain
tautologies in weak proof system give upper bounds on the computational complexity of …

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

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 …

Let L be a first-order language and Φ and Ψ two L-sentences that cannot be satisfied
simultaneously in any finite L-structure. Then obviously the following principle ChainL, Φ, Ψ …

A teoria de complexidade computacional procura estabelecer limites para a eficiência dos
algoritmos, investigando a dificuldade inerente dos problemas computacionais. O problema …

We shall discuss several situations in which it is possible to extract from a proof, be it a proof
in a first-order theory or a propositional proof, some feasible computational information …

This document's goal is to interpret Soltys' theory LAp [SK01, SC04] two times. Once over the
field F2 into the theory V⊕ L, and once over the integral domain Z into the theory V# L …

Efficient characteristic set methods for computing solutions of polynomial equation systems
in a finite field are proposed. The concept of proper triangular sets is introduced and an …

Simulation of Gi with prenex cuts Page 1 Simulation of Gi with prenex cuts Emil Jerábek∗
Phuong Nguyen† November 25, 2010 Abstract We show that the quantified propositional proof …