zbMATH — the first resource for mathematics

On complexity of propositional logics. (Russian) Zbl 0615.03023
Complexity problems of mathematical logic, Collect. sci. Works, Kalinin 1985, 80-90 (1985).
[For the entire collection see Zbl 0596.00004.]
This paper enlarges and continues an earlier one of the same author [”Polynomial finite approximability of modal and superintuitionistic logics” (Russian), Mat. Logika, Mat. Ling., Teor. Algor., Kalinin. Gos. Univ., Kalinin, 75-83 (1983)]. Taking as complexity function of a logic L the function \(f_ L:\omega \to \omega\) with \(f_ L(n)\) the minimal cardinality of countermodels for all non-theorems of L of length \(\leq n\), it is shown in a first part that some intermediate logics and also some modal logics may have rapidly growing complexity functions. In a second part, the NP- reps. PSPACE-completeness of the satisfiability problem is proved for some intermediate logics.
Reviewer: S. D. Latow

03D15 Complexity of computation (including implicit computational complexity)
03B55 Intermediate logics
03B45 Modal logic (including the logic of norms)