Yes, you're absolutely right. The other excerpt paragraph right next to it is correct but terribly misleading: > That "undecidable" part is what makes this pro

Yes, you're absolutely right. The other excerpt paragraph right next to it is correct but terribly misleading: > That "undecidable" part is what makes this problem [the Halting Problem] NP-hard. I mean, that's true - but it's very misleading. The most common context in which NP-hardness is discussed is when talking about NP-complete problems - those that are NP-hard and in NP. The way you go about showing that a problem X is NP-complete is showing that it's in NP (most of the time, this is the easy bit) and then showing that it's at least as hard as some NP-complete problem Y. This is usually done by transforming an arbitrary instance of Y into an instance of X in (deterministic) polynomial time, and showing that the X-instance is satisfiable iff (<=>) the Y-instance is. Then there are problems for which NP-hardness has been shown but it's unclear whether they're in NP. Those are often of a continuous nature. I think deciding whether a level of Super Mario World is doable falls into this category.