Implicit proofs

DOI10.2178/jsl/1082418532zbMath1069.03053OpenAlexW4239243811MaRDI QIDQ5311729

Jan Krajíček

Publication date: 29 August 2005

Published in: Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.2178/jsl/1082418532

zbMATH Keywords

propositional proof systembounded arithmetic theoryexponentially long \(P\)-proofs

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) First-order arithmetic and fragments (03F30) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Complexity of proofs (03F20)

Related Items (7)

The NP Search Problems of Frege and Extended Frege Proofs ⋮ TFNP: An Update ⋮ INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH ⋮ Towards a Unified Complexity Theory of Total Functions ⋮ On meta complexity of propositional formulas and propositional proofs ⋮ Towards a unified complexity theory of total functions ⋮ CONSISTENCY OF CIRCUIT EVALUATION, EXTENDED RESOLUTION AND TOTAL NP SEARCH PROBLEMS

Cites Work

• Exponentiation and second-order bounded arithmetic
• Propositional proof systems, the consistency of first order theories and the complexity of computations
• Quantified propositional calculi and fragments of bounded arithmetic
• The relative efficiency of propositional proof systems

This page was built for publication: Implicit proofs