Complexity of the variable-free fragments of non-normal modal logics (extended version) The research is supported by the MSHE “Priority 2030” strategic academic leadership program. The paper is an extended version of the abstracts submitted to the conference Smirnov Readings [ 7 ] .
A. Kudinov, M. Rybakov · 2025
Read Complexity of the variable-free fragments of non-normal modal logics (extended version) The research is supported by the MSHE “Priority 2030” strategic academic leadership program. The paper is an extended version of the abstracts submitted to the conference Smirnov Readings [ 7 ] . by A. Kudinov, M. Rybakov (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-09136.txt.
Introduction
A Kudinov and M Rybakov weigh the cost of a logic task with no free names in a 2025 paper. The logics at stake widen plain proof rules with a may-must pair, in weak forms. The task asks if a name-free claim can be met at all in such a logic.
For each such logic that holds plain rules and sits in one weak frame, the task is hard in a set sense. Four named weak logics get an exact hard grade in the results. The grade pins the price of this stripped logic task for the first time.
Catalog record
| CREATOR | A. Kudinov, M. Rybakov |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 14 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-09136
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Complexity of the variable-free fragments of non-normal modal logics (extended version) The research is supported by the MSHE “Priority 2030” strategic academic leadership program. The paper is an extended version of the abstracts submitted to the conference Smirnov Readings [ 7 ] . A. Kudinov, M. Rybakov Abstract We show that the satisfiability problem for the variable-free fragment of every modal logic containing classical propositional logic and contained in the weak Grzegorczyk logic is NP \mathrm{NP} -hard. In particular, the variable-free fragments of the non-normal modal logics 𝐄 \mathbf{E} , 𝐄𝐌 \mathbf{EM} , 𝐄𝐍 \mathbf{EN} , and 𝐄𝐌𝐍 \mathbf{EMN} are coNP \mathrm{coNP} -complete. Modal logic is widely used in philosophy to analyze and formalize various categories related to possibility, necessity, knowledge, obligations, time, and other concepts. When interpreting knowledge, logics between \mathbf{S4} and \mathbf{S5} are often used, but sometimes weaker systems are considered, down to the minimal normal modal logic \mathbf{K} . For interpreting “belief”, logics without the axiom \Box p\to p are frequently employed. All these modal logics are normal, and they imply an agent’s ability to perform arbitrarily long and complex logical deductions. Indeed, normality, i.e., the presence of the formula \Box(p\to q)\to(\Box p\to\Box q) , essentially means the agent’s knowledge is closed under modus ponens. When combined with the necessitation rule and the classical tautologies, this implies that the agents know (or believe in) all logical consequences of their knowledge. The study of knowledge and belief for agents without “logical omniscience” necessarily leads us to non-normal modal logics. A good overview of the use of non-normal modal logics in philosophy can be found in [ 9 ] . A crucial property of a formal logical system is its computational complexity. Low complexity enables efficient use of the system in various practical applications analyzing agents’ beliefs and/or knowledge. Studying fragments with a finite set of variables provides better insight into how this complexity is structured and the potential feasibility (or impossibility) of creating more efficient algorithms. Many modal and superintuitionistic propositional logics are \mathrm{PSPACE} -hard [ 8 , 16 , 2 ] , and often \mathrm{PSPACE} -hardness can be proven for their two-variable fragments, one-variable fragments or even variable-free fragments [ 15 , 6 , 17 , 3 , 14 , 10 , 11 , 12 , 13 ] . However, when adding axioms that limit the height or width of Kripke frames, we obtain “strong” logics with \mathrm{NP} -complete satisfiability problems. For example, the logics \mathbf{K5} , \mathbf{KD45} , \mathbf{S5} , \mathbf{K4.3} , \mathbf{S4.3} , \mathbf{GL.3} , \mathbf{Grz.3} , and many others are \mathrm{coNP} -complete (see, e.g., [ 4 , Chapter 18] ). A similar situation arises when the logic is “weak”. As an example, consider the non-normal modal logic \mathbf{E} , obtained by closing the classical logic \mathbf{Cl} under substitution and the rule \frac{A\leftrightarrow B}{\Box A\leftrightarrow\Box B}. The logic \mathbf{E} is contained in the minimal normal modal logic \mathbf{K} , yet its satisfiability problem is the same as for \mathbf{Cl} , i.e., \mathrm{NP} -complete [ 18 ] . The following axioms are often added to \mathbf{E} : \begin{array}[]{lcl}\bm{am}&=&\Box(p\land q)\to\Box p;\\ \bm{ac}&=&\Box p\land\Box q\to\Box(p\land q);\\ \bm{an}&=&\Box\top.\end{array} The nomenclature of non-normal logics is typically constructed by appending to the logic’s name the second letters of the added axioms. For example, \mathbf{EMN}=\mathbf{E}+\bm{am}+\bm{an} . Logics containing the axiom \bm{am} are called monotonic, and the logic \mathbf{EMCN} coincides with the minimal normal modal logic \mathbf{K} (see [ 9 , Section 2.3] ). It is known that the logics \mathbf{K5} , \mathbf{KD45} , and \mathbf{S5} , while \mathrm{coNP} -complete in a language with countably many variables, are polynomially decidable in any language with a fixed finite number of variables, which follows from their local tabularity; the same applies to other locally tabular logics or their locally tabular fragments (e.g., the disjunction-free fragment of intuitionistic logic [ 5 ] ). At the same time, the logics \mathbf{S4.3} and \mathbf{Grz.3} remain \mathrm{coNP} -hard in a two-variable language, while \mathbf{K4.3} and \mathbf{GL.3} are hard even in a one-variable language [ 3 ] . A natural question arises: what happens to the complexity of “weak” logics when their language is restricted to a finite set of variables? In particular, what is the complexity of such fragments for the aforementioned logics? The work [ 18 ] shows that not only \mathbf{E} but also \mathbf{EM} , \mathbf{EN} , and \mathbf{EMN} are \mathrm{coNP} -complete in a language with countably many variables. Note that \mathbf{E} , \mathbf{EM} , \mathbf{EN} , and \mathbf{EMN} are not locally tabular: the formulas of the set \{\Box^{k}\bot:k\in\mathds{N}\} are pairwise non-equivalent in each of them (it suffices to observe that they are all contained in \mathbf{K} , where these formulas are pairwise non-equivalent). Using methods from [ 3 ] and generalizing results from [ 3 ] , the following theorems can be easily proved. Theorem 1 Let L be a modal logic containing \mathbf{Cl} and contained in \mathbf{Grz.3} . Then the L -satisfiability problem is \mathrm{NP} -hard for the two-variable fragment of L . Let p and q be propositional variables. Define the following formulas recursively: \begin{array}[]{lcl}\delta_{0}&=&\Box q;\\ \delta_{n+1}&=&q\wedge\Diamond(\neg q\wedge\Diamond\delta_{n}).\\ \end{array} For each n\in\mathds{N} , let \begin{array}[]{lcl}\alpha_{n}&=&\delta_{n}\wedge\neg\delta_{n+1};\\ \beta_{n}&=&\Diamond(p\wedge\alpha_{n}).\\ \end{array} Let \mathcal{P}=\{p_{k}:k\in\mathds{N}\} be a countable set of propositional variables in the language (not necessarily containing all of them). Let \bm{s} be the substitution defined for each variable r as follows: \begin{array}[]{lcl}\bm{s}r&=&\left\{\begin{array}[]{rl}\beta_{k},&\mbox{if $r=p_{k}$;}\\ r,&\mbox{if $r\not\in\mathcal{P}$.}\end{array}\right.\end{array} It is easy to see that for every classical formula \varphi with variables p_{1},\ldots,p_{n} , the following equivalence holds: \begin{array}[]{lcl}\varphi\in\mathbf{Cl}&\iff&\bm{s}\varphi\in L.\\ \end{array} ({\ast}) The implication ({\Rightarrow}) in the equivalence ({\ast}) holds because \mathbf{Cl}\subseteq L and the logic L is closed under substitution. To justify the implication ({\Leftarrow}) in the equivalence ({\ast}) , suppose that \varphi\not\in\mathbf{Cl} . Since \varphi\not\in\mathbf{Cl} , there exists a valuation v\colon\mathcal{P}\to\{0,1\} that refutes the formula \varphi . Consider the Kripke frame F=\langle\omega\cup\{\omega\},\geqslant\rangle (i.e., F is 1+\omega^{\ast} with the non-strict order 1 1 1 In fact, we may not differ \omega from \mathds{N} . ), and take a valuation such that for each k\in\omega , the following conditions hold: \begin{array}[]{lcl}k\models q&\iff&\mbox{$k$ is even;}\\ k\models p&\iff&\mbox{$k$ is even and $v(p_{k})=1$.}\\ \end{array} Then it is easy to see that for each k\in\mathds{N} , \begin{array}[]{lcl}\omega\models\beta_{k}&\iff&v(p_{k})=1,\\ \end{array} which implies that \omega\not\models\bm{s}\varphi . It remains to note that F\models\mathbf{Grz.3} , so \bm{s}\varphi\not\in\mathbf{Grz.3} , and hence \bm{s}\varphi\not\in L , since L\subseteq\mathbf{Grz.3} . Theorem 2 Let L be a modal logic containing \mathbf{Cl} and contained in \mathbf{GL.3} . Then the L -satisfiability problem is \mathrm{NP} -hard for the one-variable fragment of L . Let p be a propositional variable. Define the following formulas recursively: \begin{array}[]{lcl}\delta^{\prime}_{0}&=&\Box\bot;\\ \delta^{\prime}_{n+1}&=&\Diamond\delta_{n}.\\ \end{array} For each n\in\mathds{N} , let \begin{array}[]{lcl}\alpha^{\prime}_{n}&=&\delta^{\prime}_{n}\wedge\neg\delta^{\prime}_{n+1};\\ \beta^{\prime}_{n}&=&\Diamond(p\wedge\alpha^{\prime}_{n}).\\ \end{array} Let \mathcal{P}=\{p_{k}:k\in\mathds{N}\} be a set of propositional variables, and let \bm{s}^{\prime} be the substitution defined for each variable r as follows: \begin{array}[]{lcl}\bm{s}^{\prime}r&=&\left\{\begin{array}[]{rl}\beta^{\prime}_{k},&\mbox{if $r=p_{k}$;}\\ r,&\mbox{if $r\not\in\mathcal{P}$.}\end{array}\right.\end{array} Then, for every classical formula \varphi with variables p_{1},\ldots,p_{n} , the following equivalence holds: \begin{array}[]{lcl}\varphi\in\mathbf{Cl}&\iff&\bm{s}^{\prime}\varphi\in L.\\ \end{array} ({\ast}{\ast}) The implication ({\Rightarrow}) in the equivalence ({\ast}{\ast}) holds because \mathbf{Cl}\subseteq L and the logic L is closed under substitution. To justify the implication ({\Leftarrow}) in the equivalence ({\ast}{\ast}) , suppose that \varphi\not\in\mathbf{Cl} . Let v\colon\mathcal{P}\to\{0,1\} be a valuation that refutes the formula \varphi . Consider the Kripke frame F^{\prime}=\langle\omega\cup\{\omega\},>\rangle (i.e., F^{\prime} is 1+\omega^{\ast} with the strict order), and take a