scientific article; zbMATH DE number 3557241
From MaRDI portal
Publication:4133141
zbMath0357.68061MaRDI QIDQ4133141
Publication date: 1975
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Analysis of algorithms and problem complexity (68Q25) Classical propositional logic (03B05) Computability and recursion theory on ordinals, admissible sets, etc. (03D60)
Related Items (58)
The NP Search Problems of Frege and Extended Frege Proofs ⋮ The proof complexity of linear algebra ⋮ Dual weak pigeonhole principle, Boolean complexity, and derandomization ⋮ Expander Construction in VNC1 ⋮ Approximate counting and NP search problems ⋮ Short proofs of the Kneser-Lovász coloring principle ⋮ Unprovability of consistency statements in fragments of bounded arithmetic ⋮ ALOGTIME and a conjecture of S. A. Cook ⋮ Hardness assumptions in the foundations of theoretical computer science ⋮ INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH ⋮ Typical forcings, NP search problems and an extension of a theorem of Riis ⋮ On parallel hierarchies and \(R_k^i\) ⋮ STRICT FINITISM, FEASIBILITY, AND THE SORITES ⋮ Some consequences of cryptographical conjectures for \(S_2^1\) and EF ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Unnamed Item ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ On the complexity of finding falsifying assignments for Herbrand disjunctions ⋮ On feasible numbers ⋮ Some consequences of cryptographical conjectures for S 2 1 and EF ⋮ Logical Closure Properties of Propositional Proof Systems ⋮ Towards NP-P via proof complexity and search ⋮ Models of Bounded Arithmetic Theories and Some Related Complexity Questions ⋮ A remark on pseudo proof systems and hard instances of the satisfiability problem ⋮ Mining the surface: witnessing the low complexity theorems of arithmetic ⋮ Resolution and binary decision diagrams cannot simulate each other polynomially ⋮ A second-order system for polytime reasoning based on Grädel's theorem. ⋮ A note on SAT algorithms and proof complexity ⋮ The provably total NP search problems of weak second order bounded arithmetic ⋮ Higher complexity search problems for bounded arithmetic and a formalized no-gap theorem ⋮ The canonical pairs of bounded depth Frege systems ⋮ Theories with self-application and computational complexity. ⋮ Circuit lower bounds in bounded arithmetics ⋮ A Tight Karp-Lipton Collapse Result in Bounded Arithmetic ⋮ Propositional consistency proofs ⋮ Bounded arithmetic and the polynomial hierarchy ⋮ A bounded arithmetic AID for Frege systems ⋮ Tractability of cut-free Gentzen type propositional calculus with permutation inference ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Bounded linear logic: A modular approach to polynomial-time computability ⋮ Functional interpretations of feasibly constructive arithmetic ⋮ A new recursion-theoretic characterization of the polytime functions ⋮ Feasibly constructive proofs of succinct weak circuit lower bounds ⋮ Logics for reasoning about cryptographic constructions ⋮ On the complexity of cutting-plane proofs ⋮ CONSISTENCY PROOF OF A FRAGMENT OF PV WITH SUBSTITUTION IN BOUNDED ARITHMETIC ⋮ Polynomial time ultrapowers and the consistency of circuit lower bounds ⋮ On the correspondence between arithmetic theories and propositional proof systems – a survey ⋮ Intuitionistic propositional logic is polynomial-space complete ⋮ The complexity of Gentzen systems for propositional logic ⋮ Dynamic Symmetry Breaking by Simulating Zykov Contraction ⋮ Characterizing the Existence of Optimal Proof Systems and Complete Sets for Promise Classes ⋮ Induction rules in bounded arithmetic ⋮ Automated higher-order complexity analysis ⋮ Frege proof system and TNC° ⋮ Bounded arithmetic, proof complexity and two papers of Parikh ⋮ Unprovability of circuit upper bounds in Cook's theory PV ⋮ Substitution and Propositional Proof Complexity
This page was built for publication:
