scientific article
From MaRDI portal
zbMath0619.03037MaRDI QIDQ3755452
Publication date: 1986
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
complexityupper boundproof theorypolynomial timerelativizationcontradictionrates of growthfinitistic point of view
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15) Complexity of proofs (03F20)
Related Items
Short proofs of the Kneser-Lovász coloring principle, Unifying the model theory of first-order and second-order arithmetic via \(\mathrm{WKL}_0^\ast\), On the number of steps in proofs, On the structure of initial segments of models of arithmetic, Short proofs for slow consistency, Passive induction and a solution to a Paris-Wilkie open question, On the complexity of finding falsifying assignments for Herbrand disjunctions, Optimal proof systems imply complete sets for promise classes, Towards NP-P via proof complexity and search, TRUTH AND FEASIBLE REDUCIBILITY, The small‐is‐very‐small principle, Propositional consistency proofs, Truth definition for $\Delta _ 0$ formulas and PSPACE computations, INCOMPLETENESS IN THE FINITE DOMAIN, The Axiom System IΣ0 Manages to Simultaneously Obey and Evade the Herbrandized Version of the Second Incompleteness Theorem, Consistency statements and iterations of computable functions in \(\mathrm{I}\Sigma_1\) and PRA, Some specially formulated axiomizations for \(\mathrm{I}\Sigma _0\) manage to evade the Herbrandized version of the second incompleteness theorem, A PARAMETRIC, RESOURCE-BOUNDED GENERALIZATION OF LÖB’S THEOREM, AND A ROBUST COOPERATION CRITERION FOR OPEN-SOURCE GAME THEORY, AXIOMATIZATION OF PROVABLE n-PROVABILITY, Formalizing forcing arguments in subsystems of second-order arithmetic, The closed fragment of the interpretability logic of PRA with a constant for I\(\Sigma^1\), New formally undecidable propositions: Non-trivial lower bounds on proof complexity and related theorems
