Why isn't the Generalized Super Mario Bros. obviously in NP?

Question

It is shown in the paper: "Classic Nintendo Games are (Computationally) Hard" by Greg Aloupis, Erik D. Demaine, Alan Guo, and Giovanni Viglietta that the Generalized Super Mario Bros. (SMB, for short) video game is NP-hard.

Theorem 3.1. It is NP-hard to decide whether the goal is reachable from the start of a stage in generalized Super Mario Bros.

(When generalizing the original Super Mario Bros., we assume that the screen size covers the entire level, because the game forbids Mario from going left of the screen.)

---

However, it does not claim that SMB is in NP.

My problem: Why isn't SMB obviously in NP?

---

I came up with two reasons.

• First, the solution/certificate to SMB may be not of polynomial size, due to e.g., timing. Is this valid? If so, how to argue this point more formally?
• Second, the computer can be treated as a second player. Thus, SMB is a two-player game, which may be reasonably harder. However, are the actions of the computer player determined from the beginning of the game so that we can still regard SMB as a single-player game?

---

Related posts:

• What is the whole picture of the NP-hardness proof of Super Mario Bros?
• Why are Chess, Mario, and Go not NP-complete?

---

Added: A follow-up paper also by Erik Demaine (et al.) which shows that a generalized level of SMB is PSPACE-complete.

Answer 1

One reason why it is not obvious that reachability of SMB is NP is that we would need a complete formalization of SMB, which the paper does not provide. This makes sense, as the purpose of the paper is to showcase techniques for proving NP- and PSPACE-hardness of reachability problems in generalized video games, and to do that they only have to fully specify the portion of the video game that is nessecary for their reduction framework.

Another aspect is that a priori I would see no reason that e.g. Donkey Country would be PSPACE-hard (which the paper shows), but SMB not. Sure, likely the framework from the paper cannot be used directly to show SMB is PSPACE-hard, but that doesn't mean it isn't possible. So, it doesn't seem obvious to me why SMB is not PSPACE-hard, from which it follows that it isn't obvious that it lies in NP. (as long as you don't think it is obvious that PSPACE$\neq$NP, at least)

---

As for your specific reasons why SMB might not be in NP, the fact that other games are PSPACE-hard seems a good argument why a polynomial certificate may not exist. However, proving that there indeed cannot be a polynomial size certificate would be the same as proving PSPACE$\neq$NP, so there are no known techniques to do that.

The second reason is related to the reason why the other games are PSPACE-hard. In general, solving two-player games can be done by reasoning "If P1 makes this move in turn 1, then for all moves P2 can do, pick a move for P2 s.t. $\ldots\ldots$ at the final move, P1 wins". This is the same as determining whether there is a satisfying assignment to a boolean formula with alternating universal and existential quantifiers: the true Quantified Boolean Formula problem (QBF). QBF is a PSPACE-complete problem.

This means that a 2-player game is PSPACE-hard if the above strategy of essentially going over all the moves is the only strategy to be guaranteed to win. The strategy of the 'computer' is of course limited in being only a simple function of the current state, but such a limited strategy can apparently be enough, as in the other games that are shown to be PSPACE-hard.

---

One question that may rise is why it is obvious that the problems lie in PSPACE. The authors cover this on page 2, but I will rephrase their argument here for the sake of completeness. Their main assumption is that the size required to describe the internal game state is polynomial in the input size. Their (somewhat informal) argument for this is that state changes of the game must controlled by a 'simple' and deterministic function of the player input. From the assumption it follows that we can solve a game reachability problem by making moves nondeterministically while maintaining the current game state. This means that the problem is in NPSPACE, and therefore in PSPACE as PSPACE=NPSPACE.

Answer 2

I remember discussing that with other people, and we came to the conclusion that it might have been because the authors couldn't exhibit a certificate of polynomial size.

For example, a path that solves the level might not be of polynomial size : maybe in some cases, you need to do an exponential number of steps to complete the level.
If you can show that for any level there exists there exists a path of polynomial size (or any other polynomial certificate), then you would prove that $SMB \in \mathcal{NP}$.

Also, the interesting point in a reduction is often the NP-hard part, which changes for every problem, the membership in NP is usually a formality, an looks very similar everytime (eventhough it is necessary). The authors might have chosen to ignore that part for this reason (EDIT : and therefore only done a hardness proof, not a completeness proof).