💻 computer science

Taming Complexity in Intuitionistic Modal Logic: The Case of FIK and Its Shallow Calculus

This paper introduces a shallow sequent calculus for the intuitionistic modal logic FIK, proving its syntactic completeness and establishing an EXPSPACE upper bound for its decision problem, thereby demonstrating significantly lower complexity than the conjectured non-elementary complexity of IK.

Original authors: Han Gao (Institute of Computer Science, Czech Academy of Sciences), Nicola Olivetti (Aix-Marseille University, CNRS)

Published 2026-07-01

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Han Gao (Institute of Computer Science, Czech Academy of Sciences), Nicola Olivetti (Aix-Marseille University, CNRS)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to solve a very complex puzzle, but the rules of the game are written in a language that is slightly different from the one you are used to. This paper is about a specific type of logic puzzle called Intuitionistic Modal Logic.

To understand what the authors did, let's break it down using some everyday analogies.

The Landscape: Three Different Neighborhoods

Think of the world of these logic puzzles as a city with three distinct neighborhoods, each with its own set of rules:

The "Simple" Neighborhood (Constructive Logics): Here, the rules are straightforward. You can solve puzzles here using a standard, flat notebook. It's easy to check if a solution is correct, and it doesn't take much mental energy (computer memory) to do it.
The "Complex" Neighborhood (IK): This is the big, chaotic city. The rules here are very strict and interconnected. To solve a puzzle here, you need a notebook with infinite layers of folders inside folders (nested structures). Because the rules are so tangled, we don't even know if there's a limit to how much memory a computer needs to solve these puzzles. Some experts think it might require an impossible amount of memory.
The "Middle" Neighborhood (FIK): This is the new house the authors are studying. It sits right between the Simple and Complex neighborhoods. It has some of the strict rules of the Complex neighborhood, but it's not quite as messy. The big question was: Is this new neighborhood as hard to solve as the Complex one, or is it closer to the Simple one?

The Problem: The "Nested" Nightmare

For the Complex neighborhood, mathematicians had to invent a special tool: a Nested Calculus. Imagine trying to organize your files. In the Complex neighborhood, you have a file, inside that file is another folder, inside that is another folder, and so on, potentially forever. To prove a solution is correct, you have to keep track of all these layers. This makes the process incredibly heavy and slow for computers.

The authors asked: Can we solve the puzzles in the Middle Neighborhood (FIK) without needing these infinite layers of folders?

The Solution: The "Shallow" Calculator

The authors invented a new tool called a "Shallow Sequent Calculus."

Here is the metaphor:

The Old Way (Nested): Imagine you are looking at a map. To understand where you are, you have to look at the current street, then the city it's in, then the country, then the continent, then the galaxy, all at once. You have to hold the whole universe in your head to make a decision.
The New Way (Shallow): The authors realized that for the Middle Neighborhood, you don't need to look at the whole galaxy. You only need to look at two things:
1. The street you are currently standing on.
2. The immediate neighbors (the houses directly connected to your street).

That's it. You don't need to look at the houses two streets away, or the countries those houses belong to. You only need a "shallow" view.

How They Proved It

The authors didn't just guess this would work; they built a rigorous mathematical proof to show it:

Building the Tool: They created a set of rules (a calculus) that only allows for this "two-level" view (your current spot and your immediate neighbors).
Checking the Rules: They proved that this new, simpler tool is powerful enough to solve every puzzle that the complex, deep tool could solve. They did this by showing that you can always "cut out" the middleman steps (a process called "cut-admissibility") without losing the solution.
Measuring the Effort: They calculated how much computer memory (space) is needed to use this new tool.

The Big Result

The paper concludes that the decision problem for this Middle Neighborhood (FIK) is in EXPSPACE.

What does this mean? It means that while solving these puzzles is still very hard (it requires a lot of memory), it is not the impossible, "non-elementary" nightmare that the Complex neighborhood (IK) might be.
The Analogy: If the Complex neighborhood requires a computer to count to infinity, the Middle neighborhood only requires a computer to count to a very, very large number (like the number of atoms in the universe). It is "elementary" and manageable, whereas the other might not be.

Summary

The authors took a logic system that was suspected to be incredibly difficult and messy (like a maze with infinite corridors). They showed that by changing how we look at the maze—focusing only on the current room and the doors right next to it, rather than the entire building's history—we can solve the puzzles much more efficiently.

They proved that this specific logic system (FIK) is significantly easier to handle than its "cousin" (IK), even though they look very similar on the surface. This gives us a new, more efficient way to verify logical statements in this specific area of mathematics.

Technical Summary: Taming Complexity in Intuitionistic Modal Logic: The Case of FIK and Its Shallow Calculus

Problem Statement
Intuitionistic modal logics (IML) exhibit a significant divergence between their semantic characterizations and their proof-theoretic properties. While constructive modal logics (such as CK and WK) admit simple Gentzen calculi and possess a PSPACE decision complexity, the logic IK (Fischer Servi/Simpson's logic) requires complex nested or labeled sequent calculi. Consequently, the decision problem for IK is conjectured to be non-elementary. The logic FIK (Forward-Confluent Intuitionistic Modal Logic), introduced recently, occupies a strict intermediate position between constructive logics and IK. Semantically, FIK shares the same forcing conditions as IK (specifically, it satisfies Fischer Servi's conditions but lacks the backward confluence required for IK). However, its computational complexity remained an open question: is FIK computationally similar to the tractable constructive logics or the potentially intractable IK? Previous work provided a "bi-nested" calculus for FIK, but deriving a precise complexity upper bound from that system was non-trivial.

Methodology
The authors introduce a new proof system for FIK called SCFIK, a "shallow" sequent calculus. Unlike full nested calculi which allow arbitrary levels of nesting, SCFIK restricts sequents to at most one level of nesting.

Structure: A sequent in SCFIK consists of a top-level component (a multiset of annotated formulas) and a finite set of "blocks." Each block contains a single ordinary Gentzen sequent. This structure represents the current world and its direct accessible successors, avoiding deeper nesting.
Annotations: The calculus employs a polarized annotation system where formulas are marked as input ( $A^\bullet$ ) or output ( $A^\circ$ ).
Rules: The inference rules operate either on the top level or within a block. Rules for connectives (e.g., $\supset$ , $\wedge$ , $\vee$ , $\square$ , $\diamond$ ) appear in pairs ( $r_1, r_2$ ) to handle both levels.
Proof Search Strategy: To establish complexity bounds, the authors refine the calculus to SC $^\times_{FIK}$ , operating on "quasi-set-sequents" (sets rather than multisets). They define "tight sequents" to restrict the proof search space, ensuring that input parts of blocks are non-decreasing and preventing redundant block duplications. A specific backward proof search strategy is employed that forbids redundant rule applications and identical sequents within a branch.

Key Contributions and Results

Syntactic Completeness and Cut-Admissibility: The authors prove that SCFIK is syntactically complete with respect to the Hilbert system CFIK. This is achieved by first showing that the calculus augmented with cut rules is complete, and then proving the admissibility of the cut rules (both top-level and block-level cuts) via a complex induction on the rank of the cut formula and the height of the derivation.
Complexity Upper Bound: By analyzing the proof search in the refined calculus SC $^\times_{FIK}$ $_{F I K}^{\times}$ , the authors demonstrate that any provable formula has a "clean" derivation where every branch has an exponential length relative to the size of the formula.
- They establish that the number of distinct "tight" sequents in a branch is bounded exponentially.
- Consequently, they prove that the decision problem for FIK is in EXPSPACE.
Comparison with IK: This result places FIK significantly below the complexity conjectured for IK (which is suspected to be non-elementary), while being strictly higher than the PSPACE bound for constructive logics like CK and WK.

Significance
The paper argues that FIK is a meaningful and distinct member of the IML family. Despite sharing the forcing conditions of IK, its proof-theoretic structure allows for a significantly lower complexity bound (elementary vs. potentially non-elementary). The authors posit that the "shallow" calculus approach offers a middle ground between simple Gentzen calculi and full nested calculi, providing a viable method for establishing complexity bounds for other intuitionistic modal logics that previously required more complex systems. The work suggests that the lack of backward confluence in FIK, while semantically subtle, has profound implications for the tractability of its decision problem. The question of whether the EXPSPACE bound is tight (i.e., the lower bound) remains open, mirroring the status of the lower bound for IK.