scientific article; zbMATH DE number 819737
From MaRDI portal
Publication:4856172
zbMath0835.03025MaRDI QIDQ4856172
Publication date: 23 November 1995
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
bounded arithmeticpropositional proof systemsindependence proofslower bound proofswitnessingcomplexity of propositional logic
Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30)
Related Items
Characterizing Tseitin-Formulas with Short Regular Resolution Refutations, 1998 European Summer Meeting of the Association for Symbolic Logic, Polynomial induction and length minimization in intuitionistic bounded arithmetic, Hardness Characterisations and Size-width Lower Bounds for QBF Resolution, How to extend the semantic tableaux and cut-free versions of the second incompleteness theorem almost to Robinson's arithmetic q, Short Proofs of the Kneser-Lovász Coloring Principle, On an optimal quantified propositional proof system nal proof system and a complete language for NP ∩ co-NP for NP ∩ co-NP, Unnamed Item, Unnamed Item, 2009 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium '09, Propositional Proofs in Frege and Extended Frege Systems (Abstract), Randomized feasible interpolation and monotone circuits with a local oracle, Characterizing Propositional Proofs as Noncommutative Formulas, A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝 Frege systems], Collapsing modular counting in bounded arithmetic and constant depth propositional proofs, An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle, Unnamed Item, On feasible numbers, Logical Closure Properties of Propositional Proof Systems, Models of Bounded Arithmetic Theories and Some Related Complexity Questions, On the finite axiomatizability of, Short refutations for an equivalence‐chain principle for constant‐depth formulas, Towards Uniform Certification in QBF, ON THE EXISTENCE OF STRONG PROOF COMPLEXITY GENERATORS, END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS, Forcing in Finite Structures, Towards a Unified Complexity Theory of Total Functions, Unnamed Item, A Tight Karp-Lipton Collapse Result in Bounded Arithmetic, A new proof of the weak pigeonhole principle, Witnessing matrix identities and proof complexity, INCOMPLETENESS IN THE FINITE DOMAIN, Lower bounds for resolution and cutting plane proofs and monotone computations, Exponential Lower Bounds for AC0-Frege Imply Superpolynomial Frege Lower Bounds, A theory for Log-Space and NLIN versus co-NLIN, Parallel strategies, The Axiom System IΣ0 Manages to Simultaneously Obey and Evade the Herbrandized Version of the Second Incompleteness Theorem, Extracting Algorithms from Intuitionistic Proofs, An unexpected separation result in Linearly Bounded Arithmetic, A model of \(\widehat{R}^2_3\) inside a subexponential time resource, Weak arithmetic, Unnamed Item, The Complexity of Propositional Proofs, A Note on Conservativity Relations among Bounded Arithmetic Theories, Strengths and Weaknesses of LH Arithmetic, A Game Characterisation of Tree-like Q-resolution Size, Examining Fragments of the Quantified Propositional Calculus, The Deduction Theorem for Strong Propositional Proof Systems, Proof Complexity of Non-classical Logics, Time-Space Trade-offs in Resolution: Superpolynomial Lower Bounds for Superlinear Space, On Stronger Calculi for QBFs, Propositional proof complexity, Definability of Recursive Predicates in the Induced Subgraph Order, A Measure of Logical Inference and Its Game Theoretical Applications, On the Herbrand notion of consistency for finitely axiomatizable fragments of bounded arithmetic theories, Resolution and the binary encoding of combinatorial principles, An exploration of the partial respects in which an axiom system recognizing solely addition as a total function can verify its own consistency, Unnamed Item, Frege proof system and TNC°, LOWER BOUNDS FOR DNF-REFUTATIONS OF A RELATIVIZED WEAK PIGEONHOLE PRINCIPLE, Unnamed Item, Short Proofs for the Determinant Identities, Asymptotic invariants, complexity of groups and related problems, Monotone simulations of non-monotone proofs., Resolution lower bounds for perfect matching principles, The equivalence of theories that characterize ALogTime, The proof complexity of linear algebra, Nondeterministic functions and the existence of optimal proof systems, Dual weak pigeonhole principle, Boolean complexity, and derandomization, Short proofs of the Kneser-Lovász coloring principle, Circuit principles and weak pigeonhole variants, Proof complexity of intuitionistic implicational formulas, Hardness assumptions in the foundations of theoretical computer science, Quantified propositional calculus and a second-order theory for NC\(^{\text \textbf{1}}\), Division by zero, Partial collapses of the \(\Sigma _1\) complexity hierarchy in models for fragments of bounded arithmetic, Preservation theorems for bounded formulas, Typical forcings, NP search problems and an extension of a theorem of Riis, Uniform proofs of ACC representations, Preservation theorems and restricted consistency statements in bounded arithmetic, Proof complexity in algebraic systems and bounded depth Frege systems with modular counting, \(\text{Count}(q)\) does not imply \(\text{Count}(p)\), End extensions of models of linearly bounded arithmetic, A lower bound for the pigeonhole principle in tree-like resolution by asymmetric prover-delayer games, Some consequences of cryptographical conjectures for \(S_2^1\) and EF, Passive induction and a solution to a Paris-Wilkie open question, Relativization makes contradictions harder for resolution, Classes of representable disjoint \textsf{NP}-pairs, Generalized quantifier and a bounded arithmetic theory for LOGCFL, A saturation property of structures obtained by forcing with a compact family of random variables, Real closures of models of weak arithmetic, The limits of tractability in resolution-based propositional proof systems, Optimal proof systems imply complete sets for promise classes, Integer factoring and modular square roots, A game characterisation of tree-like Q-resolution size, Improved bounds on the weak pigeonhole principle and infinitely many primes from weaker axioms, On reducibility and symmetry of disjoint NP pairs., Algebraic proof systems over formulas., A note on propositional proof complexity of some Ramsey-type statements, Synonymous logics, On \(\epsilon\)-sensitive monotone computations, The strength of sharply bounded induction requires MSP, On the computational complexity of cut-reduction, Propositional proofs and reductions between NP search problems, A second-order system for polytime reasoning based on Grädel's theorem., 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, From QBFs to \textsf{MALL} and back via focussing, Introduction to clarithmetic. I, Parameterized proof complexity, Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem, Proof complexity of propositional default logic, New methods for 3-SAT decision and worst-case analysis, A note on uniform density in weak arithmetical theories, Theories with self-application and computational complexity., Circuit lower bounds in bounded arithmetics, Bounded theories for polyspace computability, Tuples of disjoint \(\mathsf{NP}\)-sets, Feasible operations on proofs: the logic of proofs for bounded arithmetic, Lifting lower bounds for tree-like proofs, A bounded arithmetic AID for Frege systems, Rank bounds for a hierarchy of Lovász and Schrijver, Construction of models of bounded arithmetic by restricted reduced powers, Lower bound techniques for QBF expansion, Self-verifying axiom systems, the incompleteness theorem and related reflection principles, Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution, 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, Upper and lower Ramsey bounds in bounded arithmetic, The complexity of the Hajós calculus for planar graphs, Limitations of restricted branching in clause learning, Characterising tree-like Frege proofs for QBF, Independence results for variants of sharply bounded induction, A generalization of the second incompleteness theorem and some exceptions to it, Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies, The deduction theorem for strong propositional proof systems, Understanding cutting planes for QBFs, Building strategies into QBF proofs, Some specially formulated axiomizations for \(\mathrm{I}\Sigma _0\) manage to evade the Herbrandized version of the second incompleteness theorem, Polynomial time ultrapowers and the consistency of circuit lower bounds, Quantum deduction rules, On tseitin formulas, read-once branching programs and treewidth, Short propositional refutations for dense random 3CNF formulas, Substitution Frege and extended Frege proof systems in non-classical logics, Induction rules in bounded arithmetic, Alternating minima and maxima, Nash equilibria and bounded arithmetic, Separation results for the size of constant-depth propositional proofs, Some results on cut-elimination, provable well-orderings, induction and reflection, Bounded arithmetic, proof complexity and two papers of Parikh, Structures interpretable in models of bounded arithmetic, A model-theoretic characterization of the weak pigeonhole principle, Open induction in a bounded arithmetic for \(\mathrm{TC}^{0}\), A new proof of Ajtai's completeness theorem for nonstandard finite structures, Notations for exponentiation., LA, permutations, and the Hajós calculus, Applicative theories for logarithmic complexity classes, Ordinal notations and well-orderings in bounded arithmetic, Saturated models of universal theories, On the query complexity of selecting minimal sets for monotone predicates, Relativizing small complexity classes and their theories, Hardness and optimality in QBF proof systems modulo NP
