scientific article; zbMATH DE number 4004177
From MaRDI portal
Publication:3755452
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
Cited in
(27)- Optimal proof systems imply complete sets for promise classes
- The small-is-very-small principle
- Unifying the model theory of first-order and second-order arithmetic via \(\mathrm{WKL}_0^\ast\)
- Incompleteness of boundedly axiomatizable theories
- The closed fragment of the interpretability logic of PRA with a constant for I\(\Sigma^1\)
- The axiom system \(\mathrm{I}\Sigma_{0}\) manages to simultaneously obey and evade the Herbrandized version of the second incompleteness theorem
- Towards NP-P via proof complexity and search
- AXIOMATIZATION OF PROVABLE n-PROVABILITY
- New formally undecidable propositions: Non-trivial lower bounds on proof complexity and related theorems
- On the structure of initial segments of models of arithmetic
- Incompleteness in the finite domain
- Propositional consistency proofs
- 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
- scientific article; zbMATH DE number 4187801 (Why is no real title available?)
- Passive induction and a solution to a Paris-Wilkie open question
- scientific article; zbMATH DE number 4033740 (Why is no real title available?)
- Propositional proof systems, the consistency of first order theories and the complexity of computations
- Formalizing forcing arguments in subsystems of second-order arithmetic
- Short proofs of the Kneser-Lovász coloring principle
- On the number of steps in proofs
- TRUTH AND FEASIBLE REDUCIBILITY
- Short proofs for slow consistency
- Truth definition for \(\Delta_0\) formulas and PSPACE computations
- A note on proofs of falsehood
- A parametric, resource-bounded generalization of Löb's theorem, and a robust cooperation criterion for open-source game theory
- On the complexity of finding falsifying assignments for Herbrand disjunctions
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)
