Publication:5306365
From MaRDI portal
zbMath1206.03051MaRDI QIDQ5306365
No author found.
Publication date: 9 April 2010
bounded arithmetic; witnessing theorem; proof complexity; reflection principle; complexity classes; bounded reverse mathematics
03-01: Introductory exposition (textbooks, tutorial papers, etc.) pertaining to mathematical logic and foundations
03-02: Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03F30: First-order arithmetic and fragments
68Q15: Complexity classes (hierarchies, relations among complexity classes, etc.)
03F20: Complexity of proofs
Related Items
Unnamed Item, Unnamed Item, Characterizing Propositional Proofs as Noncommutative Formulas, STRICT FINITISM, FEASIBILITY, AND THE SORITES, Achieving New Upper Bounds for the Hypergraph Duality Problem through Logic, Simulation of Natural Deduction and Gentzen Sequent Calculus, Expander Construction in VNC1, Unnamed Item, Unnamed Item, Rethinking Defeasible Reasoning: A Scalable Approach, Unnamed Item, Unnamed Item, On the finite axiomatizability of, A recursion-theoretic characterisation of the positive polynomial-time functions, Constraint Satisfaction Problems with Global Modular Constraints: Algorithms and Hardness via Polynomial Representations, Hardness Characterisations and Size-width Lower Bounds for QBF Resolution, Primitive recursive reverse mathematics, Models of VTC0$\mathsf {VTC^0}$ as exponential integer parts, Total maps of Turing categories, Reverse complexity, Superpolynomial lower bounds for the \((1+1)\) EA on some easy combinatorial problems, Corrigendum to: ``Uniform constant-depth threshold circuits for division and iterated multiplication, Characteristic set algorithms for equation solving in finite fields, A note on SAT algorithms and proof complexity, Circuit lower bounds in bounded arithmetics, Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\), Observations on complete sets between linear time and polynomial time, 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, Root finding with threshold circuits, Independence results for variants of sharply bounded induction, Short propositional refutations for dense random 3CNF formulas, Understanding cutting planes for QBFs, Real closures of models of weak arithmetic, Lower bound techniques for QBF expansion, Feasibly constructive proofs of succinct weak circuit lower bounds, The treewidth of proofs, Building strategies into QBF proofs, Expander construction in \(\mathrm{VNC}^1\), From QBFs to \textsf{MALL} and back via focussing, On the efficiency of solving Boolean polynomial systems with the characteristic set method, Partially definable forcing and bounded arithmetic, A formal framework for stringology, Induction rules in bounded arithmetic, Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\), Applicative theories for logarithmic complexity classes, A game characterisation of tree-like Q-resolution size, Elementary analytic functions in \(\mathsf{VT}\mathsf{C}^0\), A Game Characterisation of Tree-like Q-resolution Size, Build your own clarithmetic I: Setup and completeness, Unnamed Item, A form of feasible interpolation for constant depth Frege systems
