💻 computer science

Satisfiability for Knowing How over Linear Plans is NP-complete

This paper establishes that the satisfiability problem for a modal logic expressing knowing-how assertions over linear plans is NP-complete, a result achieved by translating the problem into modal logic S5.

Original authors: Carlos Areces, Pablo Barceló, Valentin Cassano, Pablo F. Castro, Stéphane Demri, Raul Fervari

Published 2026-05-20

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Carlos Areces, Pablo Barceló, Valentin Cassano, Pablo F. Castro, Stéphane Demri, Raul Fervari

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

The Big Picture: The "Knowing-How" Puzzle

Imagine you are playing a complex video game. You have a character (the agent) and a set of buttons they can press (the actions). The game world is full of different rooms and states.

The paper focuses on a specific type of question you might ask about this game: "Does my character know how to get from the starting room to the treasure room?"

In the world of computer science and logic, this is called Knowing-How. It's not just about luck; it's about having a guaranteed plan. If you press a sequence of buttons, will you always reach the treasure, no matter which path you take through the game?

The authors of this paper wanted to solve a specific puzzle: How hard is it for a computer to decide if a "Knowing-How" statement is true or false?

The Previous Problem: A Bumpy Road

Before this paper, researchers knew the answer was "hard," but they weren't sure exactly how hard.

They knew it was harder than simple math problems (which are easy for computers).
They thought it might be as hard as the "second level" of a very difficult hierarchy of problems (called $\Sigma_2^P$ or NP-NP).

Think of the previous method like trying to solve a maze by hiring two different teams of detectives. Team A guesses a path, and Team B tries to prove Team A is wrong. If Team B can't find a flaw, Team A wins. This "guess-and-check" loop is very slow and computationally expensive.

The New Discovery: A Shortcut to the Finish Line

The main result of this paper is a breakthrough: The problem is actually much easier than we thought.

The authors proved that deciding if a "Knowing-How" statement is true is NP-complete.

What does this mean? It means the problem is as hard as the hardest problems that a computer can still solve reasonably quickly (like solving a Sudoku puzzle or checking if a complex math equation has a solution).
The Analogy: Instead of hiring two teams of detectives to argue back and forth, the authors found a way to translate the "Knowing-How" question into a single, standard logic puzzle. Once translated, a computer can solve it efficiently without needing that complicated two-step guessing process.

How They Did It: The Magic Translator

The authors didn't just guess; they built a translator.

The Original Language (Knowing-How): This language is tricky because it talks about "plans" and "strong execution."
- Analogy: Imagine a plan is a recipe. "Strong execution" means the recipe works even if you accidentally drop an egg or the oven temperature fluctuates slightly. You can't just follow the steps; you have to be sure the steps always work.
The Target Language (S5 Logic): This is a simpler, well-known language used in logic for a long time. It's like a standard checklist.
The Translation: The authors showed that you can take any complex "Knowing-How" question and rewrite it as a standard checklist question.
- If the checklist can be satisfied, the original "Knowing-How" plan exists.
- If the checklist fails, no such plan exists.

Because we already know how to solve checklist problems quickly (in the NP class), this translation proves that "Knowing-How" problems can also be solved quickly.

Why This Matters: The "Small Model" Surprise

The paper also discovered something surprising about the size of the worlds where these plans work.

The Old Fear: We might have thought that to prove a character "knows how" to do something, we might need to imagine a universe with billions of rooms and infinite possibilities.
The New Reality: The authors proved that if a plan exists, it can always be found in a small universe.
- Analogy: Even if the game has infinite levels, if a winning strategy exists, you can prove it by looking at a map that is only a few pages long. You don't need to explore the whole galaxy.

The Twist: Checking vs. Solving

The paper ends with a fascinating observation about the difference between solving a problem and checking a solution.

Satisfiability (Solving): "Does a plan exist?" -> Easy (NP).
Model Checking (Verifying): "Here is a specific map and a specific plan. Does this plan work on this map?" -> Hard (PSPACE).
The Analogy:
- Solving is like asking, "Is there any way to cross the river?" (The authors found a shortcut to answer this).
- Checking is like being handed a specific bridge and asked, "Will this specific bridge hold up under a truck?" (This is still very hard to verify because you have to simulate every single step of the truck crossing).

It is rare in computer science for the "Is there a solution?" question to be easy, while the "Does this specific solution work?" question is hard. The authors explain that this happens because "Knowing-How" relies on the existence of a perfect plan, but verifying that plan requires simulating every possible twist and turn, which is computationally heavy.

Summary

The Goal: Determine if an agent has a guaranteed plan to reach a goal.
The Result: This is NP-complete. It is solvable efficiently, not requiring the complex, multi-layered guessing methods used before.
The Method: Translate the complex "Knowing-How" logic into a simpler, standard logic (S5) that computers already know how to handle.
The Bonus: If a plan exists, it can be proven using a relatively small model (a small map), not an infinite one.

The paper effectively closes the gap on how hard this specific type of logical reasoning is, moving it from the "very difficult" category to the "manageable but complex" category.

Problem Statement
This paper investigates the computational complexity of the satisfiability problem for $\mathfrak{L}(\mathsf{Kh})$ , a modal logic designed to express "knowing-how" assertions. Introduced by Wang (2015, 2018), this logic captures an agent's ability to achieve a goal $\psi$ given a precondition $\varphi$ via the modality $\mathsf{Kh}(\varphi, \psi)$ . Semantically, this holds if there exists a linear plan that is strongly executable (guaranteed to complete regardless of execution path) from all states satisfying $\varphi$ and leads to states satisfying $\psi$ . While the logic is foundational for reasoning about strategies in AI and automated planning, its exact computational complexity remained open. Previous work by Areces et al. (2023) established an upper bound of $\mathsf{NP}^{\mathsf{NP}}$ (the second level of the polynomial hierarchy, $\Sigma^P_2$ ), leaving a gap between this upper bound and the known $\mathsf{NP}$ -hardness derived from propositional logic.

Methodology
The authors resolve this complexity gap by developing a direct translation from $\mathfrak{L}(\mathsf{Kh})$ to a simpler logic, $\mathfrak{L}(\mathsf{A})$ , which is a syntactic variant of the modal logic S5 extended with global universal modalities. The core methodological innovation is avoiding the unsatisfiability checks used in previous approaches, which necessitated the higher complexity bound.

The proof proceeds through the following technical steps:

Decomposition: The satisfiability of an arbitrary $\mathfrak{L}(\mathsf{Kh})$ formula is reduced to checking the satisfiability of a conjunction of "atoms" (positive atoms of the form $\mathsf{Kh}(\psi, \chi)$ and negative atoms of the form $\neg\mathsf{Kh}(\psi, \chi)$ ).
Translation to $\mathfrak{L}(\mathsf{A})$ :
- Positive Atoms: A conjunction of positive atoms is shown to be satisfiable if and only if a corresponding $\mathfrak{L}(\mathsf{A})$ formula is satisfiable. This formula asserts that for each $\mathsf{Kh}(\psi_i, \chi_i)$ , either the precondition $\psi_i$ is false everywhere ( $\mathsf{A}\neg\psi_i$ ) or the postcondition $\chi_i$ is true somewhere ( $\mathsf{E}\chi_i$ ).
- Negative Atoms: A conjunction of negative atoms is reduced to the satisfiability of existential formulas $\mathsf{E}(\psi_j \land \neg\chi_j)$ , ensuring that for each negated knowing-how claim, there exists a state where the precondition holds but the postcondition does not.
- Interaction Handling: To handle the interaction between positive and negative atoms, the authors introduce a partition of indices and a reflexive-transitive closure relation. This allows the construction of a complex $\mathfrak{L}(\mathsf{A})$ formula that captures potential contradictions between witness plans for positive atoms and the requirements of negative atoms.
Complexity Reduction: Since the satisfiability problem for $\mathfrak{L}(\mathsf{A})$ (equivalent to S5) is known to be $\mathsf{NP}$ -complete (Ladner, 1977), and the translation preserves satisfiability while remaining polynomial in size, the satisfiability of $\mathfrak{L}(\mathsf{Kh})$ is placed within $\mathsf{NP}$ .

Key Contributions and Results

Optimal Complexity Bound: The primary result is that the satisfiability problem for $\mathfrak{L}(\mathsf{Kh})$ is $\mathsf{NP}$ -complete. This refines the previous $\Sigma^P_2$ upper bound, establishing the exact complexity class.
Polynomial-Size Model Property: As a direct consequence of the $\mathsf{NP}$ membership proof, the paper establishes that if a formula is satisfiable, it has a model (a Labelled Transition System) of polynomial size with respect to the formula length. Specifically, the size of the state space is bounded by $O(|\varphi|^3)$ .
Technical Simplification: The authors provide a direct translation to S5-based logic, eliminating the need for the unsatisfiability checks that characterized the previous $\mathsf{NP}^{\mathsf{NP}}$ algorithm.
Expressivity: The paper confirms that $\mathfrak{L}(\mathsf{Kh})$ is strictly more expressive than $\mathfrak{L}(\mathsf{A})$ over Labelled Transition Systems, thereby extending the frontier of logics known to have $\mathsf{NP}$ -complete satisfiability.

Significance and Claims
The paper claims to close a significant complexity gap in the study of knowing-how logics. A notable observation highlighted by the authors is that, despite the semantic definition of $\mathsf{Kh}$ relying heavily on the existence of witness plans and the concept of strong executability, these structural features play no role in the satisfiability problem itself; they are effectively abstracted away during the translation to $\mathfrak{L}(\mathsf{A})$ .

This result is significant because it contrasts sharply with the model-checking problem for $\mathfrak{L}(\mathsf{Kh})$ , which is known to be $\mathsf{PSPACE}$ -complete (Demri and Fervari, 2023). The authors note that this divergence—where satisfiability is in $\mathsf{NP}$ but model checking is $\mathsf{PSPACE}$ -complete—is a "truly uncommon phenomenon." The paper concludes by suggesting that while the proof strategy yields an effective theoretical procedure, future work should focus on implementing this procedure for automated reasoning and evaluating its practical applicability, as well as extending the strategy to other variants of knowing-how logics.