I agree with the issue ("What's bigger than a dog? THE MOON"), but I don't agree with the need to provide an example that is provably distinct from NP. We're fine providing NP-complete problems without proving that they're distinct from P.

There are lots of accessible problems that belong to spaces that probably aren't NP. One that should be familiar to most people studying CS theory is "do these two regular expressions match the same set of strings?".

---

For the Diophantine vector reachability problem... I don't really like the Quanta presentation. ("An easy-sounding problem yields numbers too big for our universe.")

First, the problem, if you describe it accurately, doesn't sound easy at all. Diophantine problems are never easy. That's why we have real numbers.

Second, the article suggests that the problem should be introduced to children by casting in in terms of several rules of exchange ("For Alice, the transition vector (−1, −1, 1, 0) would represent the exchange of an apple and a banana for a cantaloupe."). But that would make the problem trivial: you start at the origin; without a rule of "exchange" in which the other party gives you as much as you want of something for free, you're never going to leave it.

And third, many easy problems generate numbers too big for our universe. That's not unusual at all. Compare the question "how many digits of pi do you need before the potential error in calculating the volume of a sphere the size of the visible universe is less than the volume of one hydrogen atom?". Can you imagine using more digits than that? You just involved a number too big for the universe.

The article passes over this point itself:

> It’s physically impossible to write down all the digits of 2↑↑­­6 — a liability of living in such a small universe.

> Second, the article suggests that the problem should be introduced to children by casting in in terms of several rules of exchange ("For Alice, the transition vector (−1, −1, 1, 0) would represent the exchange of an apple and a banana for a cantaloupe."). But that would make the problem trivial: you start at the origin; without a rule of "exchange" in which the other party gives you as much as you want of something for free, you're never going to leave it.

I'm not sure what point you're trying to make here? That specific transition vector would be one such vector among several in a given ruleset. You're correct that for any ruleset, if I don't have at least one vector that can get me away from the origin, I'm stuck there, but then I also have to consider that I still might not be able to get to where I want to go. If I have the ruleset [(2, 0), (-4, 2)] I still can't get to (3, 5).