Lower bounds for modal logics

DOI10.2178/jsl/1191333849zbMath1125.03043OpenAlexW2116871986MaRDI QIDQ5422311

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

modal logiclower boundpropositional proof complexityfeasible interpolation

Mathematics Subject Classification ID

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

Related Items

Proof complexity of modal resolution ⋮ Proof complexity of intuitionistic implicational formulas ⋮ A lower bound for intuitionistic logic ⋮ Towards NP-P via proof complexity and search ⋮ On lengths of proofs in non-classical logics ⋮ Proof Complexity of Non-classical Logics ⋮ Substitution Frege and extended Frege proof systems in non-classical logics ⋮ On the proof complexity of logics of bounded branching

Cites Work

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