Lower bounds for modal logics

DOI10.2178/JSL/1191333849MaRDI QIDQ5422311zbMATH OpenOpenAlexFDO

Authors Pavel Hrubeš

Publication date 17 October 2007

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

Full work available at URL https://projecteuclid.org/euclid.jsl/1191333849

zbMATH Keywords

feasible interpolationlower boundmodal logicpropositional proof complexity

Mathematics Subject Classification ID

Modal logic (including the logic of norms) (03B45) Complexity of proofs (03F20)

Recommendations

• On lengths of proofs in non-classical logics
• A lower bound for intuitionistic logic
• The Complexity of Propositional Proofs
• Lifting lower bounds for tree-like proofs
• Proof complexity of non-classical logics

Cites work

• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic
• The monotone circuit complexity of Boolean functions

Cited in

(14)

• On lengths of proofs in non-classical logics
• Substitution Frege and extended Frege proof systems in non-classical logics
• Proof complexity of substructural logics
• On the proof complexity of logics of bounded branching
• PSPACE bounds for rank-1 modal logics
• Proof complexity of intuitionistic implicational formulas
• Towards NP-P via proof complexity and search
• scientific article; zbMATH DE number 1088193 (Why is no real title available?)
• Some exponential lower bounds on formula-size in modal logic
• Frame-validity games and lower bounds on the complexity of modal axioms
• Proof complexity of non-classical logics
• A simplified lower bound for implicational logic
• Proof complexity of modal resolution
• A lower bound for intuitionistic logic

This page was built for publication: Lower bounds for modal logics

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