scientific article; zbMATH DE number 819737

Publication date: 23 November 1995

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

bounded arithmetic propositional proof systems independence proofs lower bound proofs witnessing complexity of propositional logic

Mathematics Subject Classification ID

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 (only showing first 100 items - show all)

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

This page was built for publication: