scientific article; zbMATH DE number 5691440

No author found.

Publication date: 9 April 2010

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

bounded arithmetic witnessing theorem proof complexity reflection principle complexity classes bounded reverse mathematics

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations (03-01) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (53)

Hardness Characterisations and Size-width Lower Bounds for QBF Resolution ⋮ Total maps of Turing categories ⋮ Reverse complexity ⋮ Superpolynomial lower bounds for the $(1+1)$ EA on some easy combinatorial problems ⋮ Expander Construction in VNC1 ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Characterizing Propositional Proofs as Noncommutative Formulas ⋮ STRICT FINITISM, FEASIBILITY, AND THE SORITES ⋮ Corrigendum to: ``Uniform constant-depth threshold circuits for division and iterated multiplication ⋮ Expander construction in $\mathrm{VNC}^1$ ⋮ Primitive recursive reverse mathematics ⋮ Unnamed Item ⋮ Real closures of models of weak arithmetic ⋮ Models of VTC0$\mathsf {VTC^0}$ as exponential integer parts ⋮ Characteristic set algorithms for equation solving in finite fields ⋮ A game characterisation of tree-like Q-resolution size ⋮ On the finite axiomatizability of ⋮ Observations on complete sets between linear time and polynomial time ⋮ A note on SAT algorithms and proof complexity ⋮ On theories of bounded arithmetic for $\mathrm{NC}^1$ ⋮ The provably total NP search problems of weak second order bounded arithmetic ⋮ The strength of extensionality. II: Weak weak set theories without infinity ⋮ Build your own clarithmetic I: Setup and completeness ⋮ Elementary analytic functions in $\mathsf{VT}\mathsf{C}^0$ ⋮ From QBFs to \textsf{MALL} and back via focussing ⋮ On the efficiency of solving Boolean polynomial systems with the characteristic set method ⋮ Circuit lower bounds in bounded arithmetics ⋮ Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic ⋮ Lower bound techniques for QBF expansion ⋮ A form of feasible interpolation for constant depth Frege systems ⋮ Root finding with threshold circuits ⋮ Conservative fragments of ${{S}^{1}_{2}}$ and ${{R}^{1}_{2}}$ ⋮ Partially definable forcing and bounded arithmetic ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ The treewidth of proofs ⋮ Independence results for variants of sharply bounded induction ⋮ Simulation of Natural Deduction and Gentzen Sequent Calculus ⋮ Unnamed Item ⋮ Understanding cutting planes for QBFs ⋮ Building strategies into QBF proofs ⋮ A Game Characterisation of Tree-like Q-resolution Size ⋮ Rethinking Defeasible Reasoning: A Scalable Approach ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ A formal framework for stringology ⋮ A recursion-theoretic characterisation of the positive polynomial-time functions ⋮ Induction rules in bounded arithmetic ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Open induction in a bounded arithmetic for $\mathrm{TC}^{0}$ ⋮ Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations ⋮ Applicative theories for logarithmic complexity classes

This page was built for publication: