[cynicaldevil]

I don't understand this, AFAIK a problem is NP-Hard or NP-Complete (or P) in _general_, that is, over all instances. But not so for a specific instance. Wouldn't these games count as just one specific instance of the problem?

[ggggtez]

The papers actually say "The rulesets allow the creation of levels which can encode an NP Hard problem". That just means if you know the answer, it's fast to show it, but finding the answer takes a lot of time.

Usually this boils down to creating AND/OR gates using level tiles, and combining them together to form arbitrary computational problems. Usually 3-SAT, because it's straight forward to encode in logic gates.

[yorwba]

It depends on whether you regard the game as limited to the pre-defined levels or allow new levels to be constructed using the same rules. The constructions discussed in the article are all about encoding NP-Complete problems in new level layouts, such that the player has to make a series of irrevocable decisions that need to encode a solution to the NP problem in order to solve the level.

[j2kun]

NP hardness is not about every instance being hard. It's a worst case notion. The paper provides an infinite family of instances which are hard assuming P is not NP. Any poly time algorithm solving for all instances has to solve those hard instances too, hence the game is hard in general.