Tabular intermediate logics comparison
Paweł Rzążewski, Michał Stronkowski · 2025
Read Tabular intermediate logics comparison by Paweł Rzążewski, Michał Stronkowski (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-2509-06841.txt.
Introduction
Comparing two logical systems defined by finite ordered sets is shown to be computationally hard in general by Paweł Rzążewski and one co-author in a 2025 logic paper. Tabular intermediate logics arise from finite posets read as Kripke frames. The containment problem asks whether every theorem of one such logic is a theorem of another.
A classic theorem links containment to the existence of surjective p-morphisms between the frames, and both problems sit inside the class NP. The authors build a translation from graphs to posets that preserves the relevant morphism existence, importing hardness results from graph theory. Several restricted versions of both problems are then NP-complete, including containment against one fixed eighteen-element poset. On the positive side, they give a polynomial-time algorithm when one of the posets is a tree, a useful tractable case.
Catalog record
| CREATOR | Paweł Rzążewski, Michał Stronkowski |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 40 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-06841
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Tabular intermediate logics comparison This preprint has not undergone peer review or any post-submission improvements or corrections. The Version of Record of this contribution is published in Proceeding of WoLLIC 2025, LNCS 15942 [ 19 ] , and is available online at https://doi.org/10.1007/978-3-031-99536-1_20 Paweł Rzążewski, Michał Stronkowski Abstract Tabular intermediate logics are intermediate logics characterized by finite posets treated as Kripke frames. For a poset ℙ \mathbb{P} , let L ( ℙ ) L(\mathbb{P}) denote the corresponding tabular intermediate logic. We investigate the complexity of the following decision problem LogContain : given two finite posets ℙ \mathbb{P} and ℚ \mathbb{Q} , decide whether L ( ℙ ) ⊆ L ( ℚ ) L(\mathbb{P})\subseteq L(\mathbb{Q}) . By Jankov’s and de Jongh’s theorem, the problem LogContain is related to the problem SPMorph : given two finite posets ℙ \mathbb{P} and ℚ \mathbb{Q} , decide whether there exists a surjective p p -morphism from ℙ \mathbb{P} onto ℚ \mathbb{Q} . Both problems belong to the complexity class NP. We present two contributions. First, we describe a construction which, starting with a graph 𝔾 \mathbb{G} , gives a poset 𝖯𝗈𝗌 ( 𝔾 ) {\sf Pos}(\mathbb{G}) such that there is a surjective locally surjective homomorphism (the graph-theoretic analog of a p p -morphism) from 𝔾 \mathbb{G} onto ℍ \mathbb{H} if and only if there is a surjective p p -morphism from 𝖯𝗈𝗌 ( 𝔾 ) {\sf Pos}(\mathbb{G}) onto 𝖯𝗈𝗌 ( ℍ ) {\sf Pos}(\mathbb{H}) . This allows us to translate some hardness results from graph theory and obtain that several restricted versions of the problems LogContain and SPMorph are NP-complete. Among other results, we present a 18-element poset ℚ \mathbb{Q} such that the problem to decide, for a given poset ℙ \mathbb{P} , whether L ( ℙ ) ⊆ L ( ℚ ) L(\mathbb{P})\subseteq L(\mathbb{Q}) is NP-complete. Second, we describe a polynomial-time algorithm that decides LogContain and SPMorph for posets 𝕋 \mathbb{T} and ℚ \mathbb{Q} , when 𝕋 \mathbb{T} is a tree. 1 Introduction A (propositional) intermediate logic is a logic, i.e., a set of formulas closed under substitutions and Modus Ponens , lying between intuitionistic and classical logics. (See e.g. [ 4 , 17 ] for the necessary information on logic, [ 21 ] on the theory of computation, [ 9 ] on graph theory and [ 13 ] on posets. The essential concepts for this article are presented in Section 2 .) Every poset \mathbb{P} determines an intermediate logic L(\mathbb{P}) . It consists of formulas that are true in \mathbb{P} when \mathbb{P} is interpreted as a Kripke frame. If \mathbb{P} is finite, we say that L(\mathbb{P}) is tabular . We are interested in comparing such logics with respect to inclusion. In particular, we investigate the computational complexity of the following decision problem Problem: LogContain Instance: A pair \mathbb{P} , \mathbb{Q} of finite posets Question: Does it hold that L(\mathbb{P})\subseteq L(\mathbb{Q}) ? In [ 16 ] it was indicated that LogContain is NP-complete even under the restriction that the input posets have depth at most three. This is the starting point of our investigations: we are interested in understanding what makes instances of LogContain hard. The problem LogContain is intrinsically related to p -morphisms, as we proceed to explain. Let \mathbb{P} and \mathbb{Q} be posets. A p -morphism (known also as a bounded morphism or a reduction) between \mathbb{P} and \mathbb{Q} is a mapping h\colon X^{\mathbb{P}}\to X^{\mathbb{Q}} satisfying (HP) for all x,y\in X^{\mathbb{P}} , if x\leq^{\mathbb{P}}y then h(x)\leq^{\mathbb{Q}}h(y) ( the homomorphism property ); (BP) for all x\in X^{\mathbb{P}} and y\in X^{\mathbb{Q}} , if h(x)\leq^{\mathbb{Q}}y then there exists z\in X^{\mathbb{P}} such that x\leq^{\mathbb{P}}z and h(z)=y ( the backward property ). Let us recall crucial Jankov’s and de Jongh’s theorem [ 14 , 8 , 7 ] . Here {\uparrow}^{\mathbb{P}}x , for an element x of a poset \mathbb{P} , denotes the upset in \mathbb{P} generated by x . Theorem 1.1 . For every finite rooted poset \mathbb{P} there exists a formula \chi_{\mathbb{P}} such that, for each poset \mathbb{Q} , we have \chi_{\mathbb{P}}\not\in L(\mathbb{Q}) if and only if \mathbb{P} is a p -morphic image of {\uparrow}^{\mathbb{Q}}x for some x\in X^{\mathbb{Q}} . Theorem 1.1 allows us, while studying LogContain , to focus only on p -morphisms, as the following direct corollary shows. Corollary 1.2 . Let \mathbb{P} and \mathbb{Q} be finite posets. Then L(\mathbb{P})\subseteq L(\mathbb{Q}) if and only if every poset {\uparrow}^{\mathbb{Q}}y , where y is minimal in \mathbb{Q} , is a p -morphic image of {\uparrow}^{\mathbb{P}}x for some x\in X^{\mathbb{P}} . In particular, if both \mathbb{P} and \mathbb{Q} are rooted and have the same depth, then L(\mathbb{P})\subseteq L(\mathbb{Q}) if and only if there is a surjective p -morphism from \mathbb{P} onto \mathbb{Q} . The above considerations lead us to the following decision problem: Problem: SPMorph Instance: A pair \mathbb{P} , \mathbb{Q} of finite posets Question: Does there exist a surjective p -morphism h\colon\mathbb{P}\to\mathbb{Q} ? It is evident that SPMorph belongs to the complexity class NP. By Corollary 1.2 , the same holds for LogContain . Graph-theoretic analogs of p -morphisms were studied in social sciences as early as the 1980s and 1990s, see e.g. [ 10 , 18 , 22 ] . They appeared under various names, like locally surjective homomorphisms , role assignments or role colorings . Computational aspects of locally surjective (and related locally bijective) graph homomorphisms were studied in e.g. [ 2 , 3 , 5 , 11 , 15 , 18 ] . (See e.g. [ 1 ] for historical information on p -morphisms.) Our main contribution in this paper is the constructions that, for a graph \mathbb{G} , produces a poset \operatorname{Pos}(\mathbb{G}) and a rooted poset \operatorname{Pos}_{\bot}(\mathbb{G}) , each of size linear in the size of \mathbb{G} , such that the following conditions are equivalent (see Theorem 3.1 and Corollary 3.10 ): • There exists a surjective locally surjective homomorphism from \mathbb{G} onto \mathbb{H} ; • There exists a surjective p -morphism from \operatorname{Pos}(\mathbb{G}) onto \operatorname{Pos}(\mathbb{H}) ; • There exists a surjective p -morphism from \operatorname{Pos}_{\bot}(\mathbb{G}) onto \operatorname{Pos}_{\bot}(\mathbb{H}) . This allows us to transfer some hardness results from graphs to posets. We summarize them below. In what follows, by (\mathbb{P}\mathrm{ath}_{2} we denote the three-vertex path and by \mathbb{K}_{4} we denote the complete graph on four vertices. The Hasse diagram of \operatorname{Pos}_{\bot}(\mathbb{P}\mathrm{ath}_{2}) is depicted in Figure 1 (some edges are plotted as dashed to improve visibility). Theorem 1.3 . The problem LogContain is NP-complete even for inputs \mathbb{P},\mathbb{Q} , where 1. \mathbb{P} is of depth 5 and \mathbb{Q}=\operatorname{Pos}_{\bot}(\mathbb{P}\mathrm{ath}_{2}) ( in particular, \mathbb{Q} has 18 elements ) ; 2. \mathbb{P} is of dimension at most 7, and its every element except for the root has at most 4 immediate successors and at most 12 successors in all, and \mathbb{Q}=\operatorname{Pos}_{\bot}(\mathbb{K}_{4}) ( in particular, \mathbb{Q} has 29 elements ) ; 3. \mathbb{P} has pathwidth at most 20 and \mathbb{Q} has pathwidth at most 17. Theorem 1.4 . The problem SPMorph is NP-complete even for inputs \mathbb{P},\mathbb{Q} , where 1. \mathbb{P} is of depth 4 and \mathbb{Q}=\operatorname{Pos}(\mathbb{P}\mathrm{ath}_{2}) ( in particular \mathbb{Q} , has 17 elements ) ; 2. \mathbb{P} is of dimension at most 7, and its every element has at most 4 immediate successors and at most