> For the complete documentation index, see [llms.txt](https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/part-ii-background/chapter-3/3-2-complexity.md).

# 3.2 Computational Complexity

Understanding the computational complexity of planning is not merely academic. It tells us which problems are tractable, where heuristics are necessary, and why neuro-symbolic approaches that learn to approximate hard subproblems are valuable. The key results for classical (STRIPS/PDDL) planning are from the foundational work of Bylander (1994); complexity results for HTN planning are covered in §3.4.

## Plan Existence — PSPACE-Complete

**Problem:** Given $\Pi = \langle F, A, I, G \rangle$, does a plan exist?

**Complexity:** PSPACE-complete (Bylander, 1994).

This means the problem is at least as hard as any problem solvable in polynomial space. PSPACE is believed to be strictly harder than NP: the state space can be exponential in the size of $F$ (there are $2^{|F|}$ possible states), and a search must navigate this space.

The conjecture PSPACE ⊋ NP (believed but unproven) means planning is harder than problems with polynomial-length certificates. The correct intuition: planning is **in** PSPACE because you can search the reachable state space using only polynomial space at any moment (store only the current state during depth-first search, not the entire search frontier). It is **at least as hard as** NP because any satisfying assignment to a SAT instance can be encoded as a planning problem. The hardness comes from the absence of a polynomial-length certificate for non-existence (no short proof that a plan does not exist), which is why plan existence is not known to be in NP.

## Bounded-Length Plan — NP-Complete

**Problem:** Does a plan of length $\leq k$ exist?

**Complexity:** NP-complete (Bylander, 1994).

With length bounded by $k$, the search space is polynomial in $k$, and a certificate (a plan) can be verified in polynomial time (apply each action in sequence and check the goal). This is the basis for SAT-based planning approaches (see Madagascar in the Appendix), which encode planning as satisfiability over a bounded horizon.

## Optimal Plan Cost — PSPACE-Hard

**Problem:** Find a plan minimizing total action cost.

**Complexity:** PSPACE-hard (at least as hard as plan existence) (Bylander, 1994).

Cost-optimal planning is strictly harder than plan existence in practice: not only must you find *a* plan, you must find the *cheapest* plan, which may require exploring the entire reachable state space. This is the setting for Fast Downward in its optimal configuration (A\* with LM-cut heuristic — see Appendix).

## Temporal Planning — PSPACE-Hard

**Problem:** Planning with durative actions, resource usage over time, and deadline constraints.

**Complexity:** PSPACE-hard in general; temporal planning with durative actions subsumes classical planning and inherits its PSPACE-hardness, since classical planning is a special case (Bylander, 1994). With numeric fluents and continuous time effects (full PDDL 2.1+ semantics), the problem may be harder or undecidable in the general case — see discussion of decidability concerns in Fox & Long (2003, §5).

Adding temporal structure does not reduce complexity and may increase practical difficulty, as the search space now includes continuous time dimensions. Temporal planners — **OPTIC** (Benton et al., 2012) and **ENHSP** (Scala et al., 2016) — use specialized heuristics to remain practical (see Additional Resources).

## Comparing Planning with First-Order Logic

It is instructive to position planning in the landscape of formal languages and their computational properties:

| Property               | Planning (STRIPS/PDDL)     | Propositional Logic                                     | First-Order Logic                         |
| ---------------------- | -------------------------- | ------------------------------------------------------- | ----------------------------------------- |
| **Decidability**       | Decidable (finite states)  | Decidable                                               | Semi-decidable (undecidable in general)   |
| **Expressiveness**     | State changes over time    | Static truth values                                     | Full quantification over infinite domains |
| **Typical Complexity** | PSPACE-complete            | NP-complete (SAT) / co-NP-complete (tautology/validity) | Undecidable (validity)                    |
| **Grounding required** | Yes (finite instantiation) | N/A                                                     | No                                        |

Planning's key advantage over FOL for practical applications: **decidability**. Classical planning with finite state spaces is decidable — a planner will always terminate with a plan or a proof that no plan exists. Full FOL planning is undecidable. STRIPS planning achieves a practical sweet spot: more expressive than propositional logic (state change over time, action schema generality) while remaining decidable.

> \[!IMPORTANT] **Practical implication for neuro-symbolic systems:** Neural components can approximate hard planning subproblems (heuristic estimation, operator learning) without sacrificing the formal guarantees provided by the symbolic planner. The neural component need not be correct — the planner verifies correctness. A bad neural heuristic means slower solving, not incorrect solving.


---

# Agent Instructions
This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com.

## Querying This Documentation
If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter, and the optional `goal` query parameter:

```
GET https://neurosymbolicai.gitbook.io/neuro-symbolic-ai-in-practice/part-ii-background/chapter-3/3-2-complexity.md?ask=<question>&goal=<endgoal>
```

`ask` is the immediate question: it should be specific, self-contained, and written in natural language.
`goal` is optional and describes the broader end goal you are ultimately trying to accomplish on behalf of the user. GitBook uses it to tailor the answer towards what is most useful for that goal.

The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.