Implicit proofs

DOI10.2178/JSL/1082418532MaRDI QIDQ5311729zbMATH OpenOpenAlexFDO

Authors 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

bounded arithmetic theoryexponentially long \(P\)-proofspropositional proof system

Mathematics Subject Classification ID

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

Recommendations

• Almost-natural proofs
• Proving implications by algebraic approximation
• scientific article; zbMATH DE number 1761885
• Translating between implicit and explicit versions of proof
• scientific article; zbMATH DE number 4158995
• Proof complexity of intuitionistic implicational formulas
• Proofs and constructions
• Proof and canonical proof
• Proofs as Objects

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

Cited in

(16)

• Towards a unified complexity theory of total functions
• Translating between implicit and explicit versions of proof
• Implicit resolution
• scientific article; zbMATH DE number 3483592 (Why is no real title available?)
• scientific article; zbMATH DE number 1114027 (Why is no real title available?)
• Towards a Unified Complexity Theory of Total Functions
• INFORMATION IN PROPOSITIONAL PROOFS AND ALGORITHMIC PROOF SEARCH
• The NP search problems of Frege and extended Frege proofs
• TFNP: an update
• Consistency of circuit evaluation, extended resolution and total NP search problems
• Mathematical logic: proof theory, constructive mathematics. Abstracts from the workshop held November 12--17, 2023
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• From proof complexity to circuit complexity via interactive protocols
• The relative strength of \#SAT proof systems
• Iterated lower bound formulas: a diagonalization-based approach to proof complexity
• On meta complexity of propositional formulas and propositional proofs

This page was built for publication: Implicit proofs

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