scientific article; zbMATH DE number 4004177

zbMATH Open0619.03037MaRDI QIDQ3755452FDOQ3755452

Authors: Pavel Pudlák 

Publication date: 1986

Title of this publication is not available (Why is that?)

Recommendations

• scientific article; zbMATH DE number 910749
• scientific article; zbMATH DE number 4033740
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• On Gödel's theorems on lengths of proofs I: Number of lines and speedup for arithmetics
• The lengths of proofs: Kreisel's conjecture and Gödel's speed-up theorem

zbMATH Keywords

complexityproof theoryupper boundpolynomial timecontradictionrates of growthrelativizationfinitistic point of view

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity of proofs (03F20) Complexity of computation (including implicit computational complexity) (03D15)

Cited In (27)

• TRUTH AND FEASIBLE REDUCIBILITY
• Title not available (Why is that?)
• The small‐is‐very‐small principle
• Unifying the model theory of first-order and second-order arithmetic via \(\mathrm{WKL}_0^\ast\)
• Towards NP-P via proof complexity and search
• On the number of steps in proofs
• Short proofs of the Kneser-Lovász coloring principle
• AXIOMATIZATION OF PROVABLE n-PROVABILITY
• Consistency statements and iterations of computable functions in \(\mathrm{I}\Sigma_1\) and PRA
• On the structure of initial segments of models of arithmetic
• Propositional consistency proofs
• Optimal proof systems imply complete sets for promise classes
• Some specially formulated axiomizations for \(\mathrm{I}\Sigma _0\) manage to evade the Herbrandized version of the second incompleteness theorem
• Passive induction and a solution to a Paris-Wilkie open question
• Truth definition for $\Delta _ 0$ formulas and PSPACE computations
• Incompleteness of boundedly axiomatizable theories
• Formalizing forcing arguments in subsystems of second-order arithmetic
• On the complexity of finding falsifying assignments for Herbrand disjunctions
• Title not available (Why is that?)
• A note on proofs of falsehood
• The axiom system \(\mathrm{I}\Sigma_{0}\) manages to simultaneously obey and evade the Herbrandized version of the second incompleteness theorem
• Short proofs for slow consistency
• INCOMPLETENESS IN THE FINITE DOMAIN
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• The closed fragment of the interpretability logic of PRA with a constant for I\(\Sigma^1\)
• A PARAMETRIC, RESOURCE-BOUNDED GENERALIZATION OF LÖB’S THEOREM, AND A ROBUST COOPERATION CRITERION FOR OPEN-SOURCE GAME THEORY
• New formally undecidable propositions: Non-trivial lower bounds on proof complexity and related theorems

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3755452)