While VGHVI as a podcast is taking an extended and possibly permanent hiatus for the foreseeable future, that hasn’t meant several of us don’t still gather to discuss different games and topics several times a month. Two weeks ago, in fact, we discussed something tied into the greater question of defining difficulty that has been bothering me ever since then. While the question was innocently asked, the answer, which I’m still not totally sure about, has some complex mathematical theories behind trying to solve it.

It’s the title of this post: is Spelunky P or NP?

It was a question that was raised again just a few days ago during another VGHVI session. This time, it was in reference to a Medium article I’ve been sharing around called “The Astounding Link Between the P≠NP Problem and the Quantum Nature of Universe” that is reporting on the work of Arkady Bolotin and possibility of there being a threshold below which quantum physics problem are not solvable in polynomial time.

What exactly is P and NP anyway?

P in this case stands for “Polynomial time.” More generally, it is a class of problems that can be solved by a deterministic Turing machine (think a computer or similar algorithmically-driven device) in polynomial time. (We might also think of this as a “feasible” amount of time, although not always exactly.)

In a classic form, it is represented as n^2. If the input is 100 (n = 100), the total number of steps to compute something is 100 ^ 2 = 10,000.

And if we know a computer takes 1 second per step, that will be 10,000 seconds for the input of n= 100.

NP stands for “Nonpolynomial time.” It is a set of “problems solvable by a nondeterministic Turing machine in polynomial time and the class of problems verifiable by a deterministic Turing machine in polynomial time” (Wikipedia).

In its classic form, we might write this as 2^n. If the input is again 100 (n = 100), the total number of steps to compute something this way is 2^100, or approximately 1.2676506 * 10^30.

And, if we again know that a computer takes 1 second per step, that will be approximately 1.2676506 * 10^30 seconds.

Generally, with it comes to dealing with computational complexity, we want problems that are P (polynomial time). Depending on the input and problem classification, we want to be able to solve and verify a solution in minutes, hours, or at most days instead of the potential years, decades, or, in the case of several well-known problems, millions of years after the heat death of the universe.

What does this have to do with videogames?

The original question, “Is Spelunky P or NP?”, concerns the amount of randomness in Spelunky itself. Does the random layout of levels, and thus position of obstacles within those levels like enemies and the placement of the exit, add up to enough computational complexity to make “solving” a session of the game a NP problem?

To think about this, let’s make some assumptions.

Assumption 1: Playing Spelunky means conforming to its rules. A “solution” must respect the physics within the game.

Assumption 2: “Solving” a fixed, non-random level in Spelunky will take polynomial time. Given the verb set of the game and the known position of obstacles within one fixed, non-random level, it will take a polynomial amount of time to “solve” it.

Assumption 3: If Assumption 1 takes polynomial time, then “solving” an entire game of fixed, non-random levels will also take polynomial time. (Potentially a large amount of time, of course, but sill polynomial in complexity.)

Assumption 4: The algorithm that generates levels in Spelunky has an upper bound. There exists a very large but total number of all possible Spelunky levels containing all possible configurations of all obstacles within them. (Since the total length and width of Spelunky levels seem to be set numbers, this is probably the case.)

Assumption 5: “Solving” one random level in Spelunky can be done in polynomial time.

Assumption 6: If Assumption 5 is true, “solving” an entire game of random levels will also take polynomial time.

Of these five, I am the most comfortable with the first three. The first is rather obvious, but it also means that the “solution” is not one of ignoring the game’s rules and extending jumps or not taking damage from enemies. The second and third are probably true of all platformers with fixed, non-random positioning of obstacles in levels. (That’s still a large number of iterations, but probably polynomial in time to both solve and verify. And more easily parallel-able too, given a fixed level size and verb set.)

Starting with Assumption 4 is where things get complicated.

The question becomes if the randomness of the levels introduces an exponential growth in complexity per calculation per step. If we think about it as the number of possible moves, including using items and all character verbs, how much more complexity does the randomness add? How much greater is the complexity, if any, than the fixed, non-random layout?

Spelunky could be calculating a path between the start of a level and the exit. The version by Darius Kazemi certainly shows that there will always a solution path. And it is probably a safe assumption all versions use some variation of the same algorithm too.

If this is the case, the total number of calculations decreases. (The difference between finding a path and the path.) In fact, if we know the total amount of variation in cells and their likelihood to have exits, there is an increased chance of a deterministic Turing machine finding the “solution” in polynomial time.

However, we still have to account for enemy encounters and systemic noise (the chance that, even with a solution path, any one session will, because of the randomness, not have the items necessary to finish). This doesn’t negate the probability of a P solution, but does complicate trying to generalize a solution for it.

So, I’m curious: what do you, dear reader, think about all this? Any takers on trying to trying to narrow down or even figure this out? Are there any assumptions I shouldn’t have made — or even could be making instead? Is Spelunky P or NP?