scientific article
From MaRDI portal
Publication:3794177
zbMath0649.03042MaRDI QIDQ3794177
Publication date: 1986
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
computational complexitycut eliminationbounded arithmeticpolynomial hierarchyarithmetic hierarchysecond order systemsbounded quantifiersbounded recursionGödel incompleteness theoremsbounded formulas of arithmeticCook's equational theory PVlimited iterationsubsystems of Peano Arithmetic
Analysis of algorithms and problem complexity (68Q25) Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Complexity of computation (including implicit computational complexity) (03D15) Cut-elimination and normal-form theorems (03F05) First-order arithmetic and fragments (03F30) Recursive functions and relations, subrecursive hierarchies (03D20) Second- and higher-order arithmetic and fragments (03F35)
Related Items (only showing first 100 items - show all)
On the complexity of the parity argument and other inefficient proofs of existence ⋮ The equivalence of theories that characterize ALogTime ⋮ The proof complexity of linear algebra ⋮ Dual weak pigeonhole principle, Boolean complexity, and derandomization ⋮ Separations of theories in weak bounded arithmetic ⋮ A Conservation Result Concerning Bounded Theories and the Collection Axiom ⋮ Open Questions in Reverse Mathematics ⋮ Short proofs of the Kneser-Lovász coloring principle ⋮ What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)? ⋮ Herbrand analyses ⋮ Squeezing Feasibility ⋮ FRAGMENTS OF APPROXIMATE COUNTING ⋮ Propositional Proofs in Frege and Extended Frege Systems (Abstract) ⋮ A time-space hierarchy between polynomial time and polynomial space ⋮ CONSISTENCY AND THE THEORY OF TRUTH ⋮ Preservation theorems for bounded formulas ⋮ An algebraic treatment of quantifier-free systems of arithmetic ⋮ Extension and interpretability ⋮ Preservation theorems and restricted consistency statements in bounded arithmetic ⋮ Toward the limits of the Tennenbaum phenomenon ⋮ Pell equations and exponentiation in fragments of arithmetic ⋮ STRICT FINITISM, FEASIBILITY, AND THE SORITES ⋮ An exponential separation between the parity principle and the pigeonhole principle ⋮ Some consequences of cryptographical conjectures for \(S_2^1\) and EF ⋮ Passive induction and a solution to a Paris-Wilkie open question ⋮ Collapsing modular counting in bounded arithmetic and constant depth propositional proofs ⋮ Generalized quantifier and a bounded arithmetic theory for LOGCFL ⋮ The Ordering Principle in a Fragment of Approximate Counting ⋮ Expander construction in \(\mathrm{VNC}^1\) ⋮ On the complexity of finding falsifying assignments for Herbrand disjunctions ⋮ Effectiveness and provability ⋮ Logical Closure Properties of Propositional Proof Systems ⋮ Polynomially and superexponentially shorter proofs in fragments of arithmetic ⋮ Cobham recursive set functions ⋮ Admissible closures of polynomial time computable arithmetic ⋮ The strength of sharply bounded induction requires MSP ⋮ Bootstrapping. I ⋮ On the computational complexity of cut-reduction ⋮ Provability and interpretability logics with restricted realizations ⋮ A second-order system for polytime reasoning based on Grädel's theorem. ⋮ 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 ⋮ Exponentiation and second-order bounded arithmetic ⋮ A note on uniform density in weak arithmetical theories ⋮ Theories with self-application and computational complexity. ⋮ Tuples of disjoint \(\mathsf{NP}\)-sets ⋮ Feasible operations on proofs: the logic of proofs for bounded arithmetic ⋮ ON A QUESTION OF KRAJEWSKI’S ⋮ Arithmetizing uniform \(NC\) ⋮ Computing on structures ⋮ Bounded arithmetic and the polynomial hierarchy ⋮ More on Systems of Truth and Predicative Comprehension ⋮ Combinatorial principles in elementary number theory ⋮ A bounded arithmetic AID for Frege systems ⋮ Primitive recursive selection functions for existential assertions over abstract algebras ⋮ Tractability of cut-free Gentzen type propositional calculus with permutation inference ⋮ \(\text{NP}\not={co}\)-NP and models of arithmetic ⋮ P, NP, Co-NP and weak systems of arithmetic ⋮ INCOMPLETENESS IN THE FINITE DOMAIN ⋮ Construction of models of bounded arithmetic by restricted reduced powers ⋮ Towards a unified complexity theory of total functions ⋮ A contribution to the end-extension problem and the \(\Pi_ 1\) conservativeness problem ⋮ On the provability logic of bounded arithmetic ⋮ A form of feasible interpolation for constant depth Frege systems ⋮ Improving known solutions is hard ⋮ Subsystems of true arithmetic and hierarchies of functions ⋮ The unprovability of small inconsistency. A study of local and global interpretability ⋮ Polynomial-time Martin-Löf type theory ⋮ The scope of Gödel's first incompleteness theorem ⋮ Conservative fragments of \({{S}^{1}_{2}}\) and \({{R}^{1}_{2}}\) ⋮ Nested PLS ⋮ Upper and lower Ramsey bounds in bounded arithmetic ⋮ Weak theories of linear algebra ⋮ Faith \& falsity ⋮ A simple proof of Parsons' theorem ⋮ A generalization of the second incompleteness theorem and some exceptions to it ⋮ An arithmetic for polynomial-time computation ⋮ No escape from Vardanyan's theorem ⋮ Some specially formulated axiomizations for \(\mathrm{I}\Sigma _0\) manage to evade the Herbrandized version of the second incompleteness theorem ⋮ 2002 European Summer Meeting of the Association for Symbolic Logic Logic Colloquium '02 ⋮ Short propositional refutations for dense random 3CNF formulas ⋮ The counting hierarchy in binary notation ⋮ The implicit commitment of arithmetical theories and its semantic core ⋮ \(S^ i_ 3\) and \(\overset\circ V^ i_ 2(BD)\) ⋮ Alternating minima and maxima, Nash equilibria and bounded arithmetic ⋮ Non-standard finite fields over \(I\Delta_0+\Omega_1\) ⋮ Automated higher-order complexity analysis ⋮ Feasible functionals and intersection of ramified types ⋮ Multifunction algebras and the provability of \(PH\downarrow\) ⋮ Some results on cut-elimination, provable well-orderings, induction and reflection ⋮ Structures interpretable in models of bounded arithmetic ⋮ A model-theoretic characterization of the weak pigeonhole principle ⋮ Notations for exponentiation. ⋮ Degrees of Dowd-type generic oracles ⋮ Saturated models of universal theories ⋮ On measure quantifiers in first-order arithmetic ⋮ Effective inseparability and its applications ⋮ Sprague-Grundy theory in bounded arithmetic ⋮ A note on sharply bounded arithmetic ⋮ A note on typed truth and consistency assertions
This page was built for publication:
