scientific article; zbMATH DE number 3995647
[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.
- On the degree of complexity of sentential logics. II: An example of the logic with semi-negation
- The disjunction property of intermediate propositional logics
- Modal companions of intermediate propositional logics
- Computing with cylindric modal logics and arrow logics, lower bounds
- Propositional truth maintenance systems: Classification and complexity analysis
- Rules with parameters in modal logic. II.
- Computational complexity for bounded distributive lattices with negation
- On the proof complexity of logics of bounded branching
- Possibilistic logic: Complexity and algorithms
- Expressing versus proving: relating forms of complexity in logic
- Complexity Classifications for Logic-Based Argumentation
- scientific article; zbMATH DE number 5599076 (Why is no real title available?)
- scientific article; zbMATH DE number 5289966 (Why is no real title available?)
- Complexity of intuitionistic propositional logic and its fragments
- scientific article; zbMATH DE number 1047510 (Why is no real title available?)
- On the complexity of propositional quantification in intuitionistic logic
- scientific article; zbMATH DE number 2072508 (Why is no real title available?)
- The complexity of propositional modal theories and the complexity of consistency of propositional modal theories
- Logics for complexity classes
- Decision problems of some intermediate logics and their fragments
- scientific article; zbMATH DE number 6963530 (Why is no real title available?)
- scientific article; zbMATH DE number 4114609 (Why is no real title available?)
- scientific article; zbMATH DE number 757645 (Why is no real title available?)
- scientific article; zbMATH DE number 937363 (Why is no real title available?)
- Propositional logics complexity and the sub-formula property
- The complexity of disjunction in intuitionistic logic
- Propositional computability logic II
- scientific article; zbMATH DE number 6276275 (Why is no real title available?)
- scientific article; zbMATH DE number 5263419 (Why is no real title available?)
- Complexity of strict implication
- A trichotomy in the complexity of propositional circumscription
- A note on the complexity of propositional Hoare logic
- Towards logical operations research -- propositional case
- Logical operations and Kolmogorov complexity
- Complexity of admissible rules
- On meta complexity of propositional formulas and propositional proofs
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4723713)