Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-14T21:27:05.434Z Has data issue: false hasContentIssue false
  • English
  • Français

Lower bounds for modal logics

Published online by Cambridge University Press:  12 March 2014

Pavel Hrubeš
Pavel Hrubeš*
Affiliation:
Mathematical Institute, Zitna 25, 11000 Praha 1, Czech Republic, E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

We give an exponential lower bound on number of proof-lines in the proof system K of modal logic, i.e., we give an example of K-tautologies ψ1, ψ2, … s.t. every K-proof of ψi must have a number of proof-lines exponential in terms of the size of ψi. The result extends, for the same sequence of K-tautologies, to the systems K4, Gödel–Löb's logic, S andS4. We also determine some speed-up relations between different systems of modal logic on formulas of modal-depth one.

Keywords

Proof complexitymodal logiclower boundmonotone interpolation
Type
Research Article
Information
The Journal of Symbolic Logic , Volume 72 , Issue 3 , September 2007 , pp. 941 - 958
Copyright
Copyright © Association for Symbolic Logic 2007

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Alon, N. and Boppana, R., The monotone circuit complexity of Boolean functions, Combinatorial, vol. 7 (1987), no. 1, pp. 1–22.CrossRefGoogle Scholar
[2]Buss, S. R., Polynomial size proofs of the propositional pigeonhole principle, this Journal, vol. 52 (1987), pp. 916–927.Google Scholar
[3]Karchmer, M., On proving lower bounds for circuit size, Proceedings of Structure in Complexity, 8th Annual Complexity Conference, IEEE Computer Science Pres, 1993, pp. 112–119.Google Scholar
[4]Krajíček, J., Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic, this Journal, vol. 62 (1997), no. 2, pp. 457–486.Google Scholar
[5]Razborov, A. A., Lower bounds on the monotone complexity of some Boolean functions, Soviet Mathematics Doklady, vol. 31 (1985), pp. 354–357.Google Scholar