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.