Author here. The owner of sokobano.de/wiki/index.php?title=Solver_Statistics is currently independently verifying the performance of my solver (and the early signs look good)!
"I think in this agentic age of software, you have to want the goal as much as the agent. Yes, anyone can build software. But you need to care about it, you need to love it. The human focus and effort remains." Great quote
It's difficult to give any strong answers. Since there's no proof that NP != PSPACE, we don't actually concretely know what the difference between the classes is, and the plain assumption that NP != PSPACE doesn't tell you where to look.
I am also not an expert on complexity theory.
But intuitively: if you try to work with these two types of problems, you find that NP-complete problems are way more amenable to _pretty good_ solutions. There are very effective SAT solvers out there, and ILP solvers. Finding a TSP solution on almost any graph on tens of thousands of nodes is quite easy, and making good adversarial instances is hard. There are many programming challenges around NP-complete problems online that attract effective solvers, e.g. PACE, and previously [:(] Google Hashcode. PSPACE-complete problems on the other hand feel really, really intractable, where even solving small instances is very difficult, and I think the article we're commenting on gives a good feeling for that.
Complexity theory has a couple of interesting "sandwiches" as a prof called them.
For example, we know that LOGTIME is a subset of PTIME, which is a subset of NPTIME and PSPACE, both of which are a subset of EXPTIME. We also know that EXPTIME is strictly bigger than LOGTIME and PTIME.
So somewhere between PTIME, NP, PSPACE and EXPTIME, there must be a change in computational capability. We just don't know where.
This also exists between constant-depth circuit networks and algorithms using LOGSPACE. A circuit network of depth of log^2(input_size) can compute more than any nondeterministic LOGSPACE algorithm, which can compute more than a circuit network of constant depth using threshold gates. We also know that a deeper circuit network has strictly more computational power than the constant depth one.
But where is the specific jump in computational power? We don't know.
That makes the "practical applications" very strange to consider.
I keep jesting, the funniest resolution of P vs NP would be that P = NP, except it has a cost factor that stops any practical collapse, like a proven minimum of O(n^<number of atoms in the universe>). That'd be the most annoying resolution of them all.
If a problem is in NP, which all NP-complete problems are, then the yes-instances of the problem have "small" solutions that can be verified efficiently.
Take sudoku. If I give you a difficult board, and also the solution, it is easy to verify that it is correct.
Small efficient certificates do not exist for PSPACE-complete problems. Indeed for Sokoban, some instances require exponentially long sequences of pushes to solve.
My first ever published game was a sokoban clone. I wrote a solver, then I used it to create levels. Since I know the best possible solution, I rate the players moves count with 1, 2 or 3 stars.
Decades ago I built a Sokoban solver, then a more generic puzzle solver which could handle a wide range of similar games (such as Atomix). It's fun to see someone else finding all of these heuristics. Excluding dead squares and searching backwards to meet in the middle I definitively implemented, and I thought of many of these others too (though whether I got around to implementing them is another question!). This post is praiseworthy for showing how intuitive these tricks are once you know them.
Agreed. If the author had used AI to write a math proof, they'd be one of those authors who could fully explain every line in the proof, and probably simplify it too. Kudos!
I was thinking about Order of the Sinking Star's state in terms of a graph. Mapping structs to vertices and edges, each vertex an instance. This is a recently released game inspired by Sokoban. Is kind of cool how you can break the whole system into a fine-grained graph encompassing all state, or extract the key state from each puzzle. Some are more conducive to this than others! I think this naturally also brings in the concept of compression, with the raw state of every item on the board being the full uncompressed version.
I did not know about Sokoban, but sounds like the rock pushing puzzle in Pokemon red/blue/yellow was inspired by it. There was this "Jev plays pokémon" livestream at some point and the model was stuck on this puzzle for hours
Baba Is You is awesome. The latest Jonathan Blow game, Order of the Sinking Star, is also about 75% sokoban puzzles by volume, and is massive. I recommend both to any puzzle fans who somehow have not played them. (Both of these games get a lot more intricate than just straightforward sokoban, in case that wasn't obvious.)
NetHack has had a bunch of Sokoban levels for many years! They are complicated by the addition of enemies that spawn for you to fight (which can block boulders you’re trying to push) as well as items that may be resting in/on the pits you’d want to push the boulders into.
We probably have to create a separate track for human only solvers and machine solvers soon.
And we will need strict rules on the human only solvers. The fun is lost when you lose to a solver written by a frontier agent swarm, while if a new solver written by a human outcompetes you, it feels all fair and square and you can go back to the drawing board.
Yes a human steered this solver, but it doesn’t feel the same competitively, like doped vs non doping athlete. Till 2026 we never had to think of this for cognitive tasks but the age to do so is coming now.
Sokoban is cool, but far from the most interesting thing here, which is the design of experiment factories for verifiable domains.
The base building blocks you need to make this work:
- dataset
- unhackable success metric
- hardened, isolated f(dataset, solver) -> metric
- helps a ton but not required: human with strong intuitive domain understanding
This is exactly the kind of RL environment in which the models are forged, so they're truly excellent at basically all stages of this process.
I'm working on something similar for image and video compression. The SOTA approach for these things currently is mostly deep neural networks. But agent powered experiment factories let you cover FAR more ground in algorithm-space than before, which makes deterministic and explicit algorithms, with little or no heuristics (aka floating point weights) feasible once again.
Explicit algorithms (SGD) grew implicit ones (neural nets) that are more powerful and general, but also more opaque and less efficient. Now those implicit ones have made search over explicit algorithms vastly faster, which is making them increasingly competitive with neural methods.
Exactly, I think algorithm development is becoming more like scientific research with hypotheses and evidence. Experiment factories is new to me but I guess it's also what I've been unconsciously developing towards after I created functional code factory for my own project.
So, quite a lot more complex than one might think.
[0] https://archim.org.uk/publications/
I'm assuming P != NP (and NP != PSPACE).
I am also not an expert on complexity theory.
But intuitively: if you try to work with these two types of problems, you find that NP-complete problems are way more amenable to _pretty good_ solutions. There are very effective SAT solvers out there, and ILP solvers. Finding a TSP solution on almost any graph on tens of thousands of nodes is quite easy, and making good adversarial instances is hard. There are many programming challenges around NP-complete problems online that attract effective solvers, e.g. PACE, and previously [:(] Google Hashcode. PSPACE-complete problems on the other hand feel really, really intractable, where even solving small instances is very difficult, and I think the article we're commenting on gives a good feeling for that.
For example, we know that LOGTIME is a subset of PTIME, which is a subset of NPTIME and PSPACE, both of which are a subset of EXPTIME. We also know that EXPTIME is strictly bigger than LOGTIME and PTIME.
So somewhere between PTIME, NP, PSPACE and EXPTIME, there must be a change in computational capability. We just don't know where.
This also exists between constant-depth circuit networks and algorithms using LOGSPACE. A circuit network of depth of log^2(input_size) can compute more than any nondeterministic LOGSPACE algorithm, which can compute more than a circuit network of constant depth using threshold gates. We also know that a deeper circuit network has strictly more computational power than the constant depth one.
But where is the specific jump in computational power? We don't know.
That makes the "practical applications" very strange to consider.
I keep jesting, the funniest resolution of P vs NP would be that P = NP, except it has a cost factor that stops any practical collapse, like a proven minimum of O(n^<number of atoms in the universe>). That'd be the most annoying resolution of them all.
Take sudoku. If I give you a difficult board, and also the solution, it is easy to verify that it is correct.
Small efficient certificates do not exist for PSPACE-complete problems. Indeed for Sokoban, some instances require exponentially long sequences of pushes to solve.
https://victorqribeiro.itch.io/qubes
I did released it for Android also, but it needs updating.
This caught me completely off-guard, and I was indeed skim reading. Nonetheless, very well written article!
That's the spirit... :-D
Maybe i will apply some of these heuristics myself when solving puzzles.
And we will need strict rules on the human only solvers. The fun is lost when you lose to a solver written by a frontier agent swarm, while if a new solver written by a human outcompetes you, it feels all fair and square and you can go back to the drawing board.
Yes a human steered this solver, but it doesn’t feel the same competitively, like doped vs non doping athlete. Till 2026 we never had to think of this for cognitive tasks but the age to do so is coming now.
The base building blocks you need to make this work:
- dataset
- unhackable success metric
- hardened, isolated f(dataset, solver) -> metric
- helps a ton but not required: human with strong intuitive domain understanding
This is exactly the kind of RL environment in which the models are forged, so they're truly excellent at basically all stages of this process.
I'm working on something similar for image and video compression. The SOTA approach for these things currently is mostly deep neural networks. But agent powered experiment factories let you cover FAR more ground in algorithm-space than before, which makes deterministic and explicit algorithms, with little or no heuristics (aka floating point weights) feasible once again.
Explicit algorithms (SGD) grew implicit ones (neural nets) that are more powerful and general, but also more opaque and less efficient. Now those implicit ones have made search over explicit algorithms vastly faster, which is making them increasingly competitive with neural methods.