Thread where we attempt to prove that Lemmings is NP-complete (split from birthday thread)

[geoo]

Yeah, seems like it's that time again. (I don't think I put my birthday into my profile, but there's at least one person that should know )

Happy birthday, Steve!
As the level design game is just in the process of being revived, here's a bonus/bogus challenge for you  (I haven't solved it myself yet, haven't thought about it too much yet) :
Design a Lemmings level scheme (arbitrary size, skills, time and amount of Lemmings) that reduces instances of an NP-complete problem to instances of Lemmings levels that are solvable iff the original problem instance is solvable, thus proving that Lemmings is NP-complete.

[Simon]

I am actually trying to come up with a NOT gate for the model/scheme I'm working on, and a way to cross wires. OR gate was easy, unless the model has to be scrapped again :]

Edit: Scratch that. Different model, easy NOT gate and crossings, but likely impossible OR >_>

-- Simon

[ccexplore]

For the Lemmings NP-Complete problem, given that we are already allowing arbitrary size for the level and number of lemmings (despite limitations in the actual game and file format), can we extend that and say we are also allowing arbitrary number of entrance trapdoors, exits, and other objects (eg. assuming that with 4+ entrances the lemmings cycle through each entrance, and that there isn't this business with "objects being fake when index > 15")?

Just wondering.  May or may not help with the problem.  Note that the ability to have arbitrary number of entrances effectively means you can directly "place" each lemming in a specific starting location in the level, by having exactly one entrance per lemming.

[ccexplore]

Let me start by saying Happy Birthday Insane Steve!   I can't believe we are hijacking this thread for geoo's pet problem. 

Now, NP-Complete Lemmings.  Here's my current, not-yet-complete (and may ultimately fail) attempt at the Lemmings NP-complete problem, assuming we can do the "one lemming per entrance (with arbitrary number of entrances)" thing.  According to Wikipedia, the partition problem is NP-complete.  I'm going to try reducing the partition problem to a suitable lemmings level.

My scheme involve splitting the start portion of the level into "units".  A "unit" basically represents an element in the multiset to partition.  The numeric value of the element translates to the number of lemmings that emerges from the unit (achieved by having each lemming come out from its own entrance, and putting the desired number of entrances in the unit).  Which partition the element can be put into is represented by having a choice of, say, 1 of 2 skills you can apply, which yields 2 choices (translating to the 2 partitions) for the location of where all lemmings from that unit will reach.

In order for this to work, we need to set things up so that in a valid solution to the level, all lemmings from a unit must all end up either all reaching location A, or all reaching location B.  It must not be the case that some can be made to reach location A while the rest reach location B.  It might be okay if some reaches A, other reaches B, but one or more remaining lemmings reach neither location and just die prematurely, if that is enough to ruin the solution.

The locations A and B are common to all units, as they represent the 2 partitions.  They lead to the end portions of the level.

The exact setup for the unit is something I'm still trying to work out.  Feel free to chime in with your stab at it.

===============

Anyway, the next part of enforcing the partitioning and summing aspect of the problem (let's say S is the target sum for each partition) is like this:

 - The goal of the level is to save at least 50% of all lemmings (ie. S lemmings).

 - Any lemming reaching location A cannot be saved no matter what, but each lemming can perform a single skill.  If S lemmings each perform the skill once, this will complete a path that allows any lemmings reaching location B to reach the exit, without performing any skills themselves.

 - There is exactly S number of that skill given in the level.  So you can't do more.  If you do any less than S, the path for B to reach exit is incomplete and you will fail to save any lemmings from B--even if you try to give the leftover skills to the B lemmings.

In other words, to save at least S lemmings, you need all of the other S lemmings to complete a path to the exit.  Those other S lemmings are sacrificed and cannot be saved no matter what you try.  Therefore, you need to ensure that you send out exactly S lemmings to location A, and the rest to location B.  If you send too many to location A, there won't be enough lemmings at location B and therefore not enough lemmings will reach the exit.  Conversely, if you send too many to location B, there won't be enough lemmings at location A to finish the path to the exit, and so no lemmings will reach the exit.

Because each unit is designed to have all lemmings belonging to it to all end up either at A or all at B, solving the level involves figuring out which combination of units to direct to A, and the other units to B, such that exactly S lemmings end up at A and the other S end up at B.  In other words, the partition problem.

Here's my current idea of enforcing this easier "summing" part of the problem, though undoubtedly there are many other ways to do this.  See attached level and replay, it's easier to explain it that way.  In this level S=5.  The 2 entrances you can think of as location A and B.  The missing part of the level (because I haven't figured out how to do it yet) is the set up of various units, each of them leading all lemmings within the unit to all go to the path corresponding to the left entrance, or all to the path corresponding to the right entrance.

==================

So what remains now is for someone to come up with a viable setup for "the unit", and then the partition problem is reduced to a lemmings level.

[ccexplore]

So what remains now is for someone to come up with a viable setup for "the unit", and then the partition problem is reduced to a lemmings level.

It just occurred to me that it's actually not too hard to create "the unit", once again assuming that we have arbitrary control over exactly where each lemming enters the level from, ie. one entrance per lemming.

The idea is to set it up so that all lemmings from a unit is compressed down to a single position.  To do that, first we make RR=99 so that it's not possible to alter the flow of lemmings that way.  You then position the entrances so that when lemming #2 from unit A lands, he lands at exactly where lemmings #1 from unit A is currently located.  Similarly, lemmings #3 will merge with lemmings #1 and 2's position when #3 comes out, and so forth.

Having all the lemmings of a unit in one place makes it easy to enforce the "all A or all B" requirement.  For example, we can have it so that after the entire unit comes out, they walk past exactly 2 places where you can dig.  Digging one place immediately leads the digger and the entire unit down a path to A, and the other place leads to B.  Everywhere else is protected from digging by steel or other such hazards, and similarly if you walk past both dig points you end up getting killed by something instead.

One other thing is, you must ensure is that you can't backroute this setup.  For example, you cannot try to use the diggers (possibly in conjunction with the blockers from the second half of the level) to prevent all lemmings from the unit compressed to a single location, and subsequently making it possible to send some of the lemmings to A and others to B.   Or, you can't use the digger to get around the second half of the level where you need to use all blockers to get exactly half the lemmings to the exit.  I particularly don't like the fact that blockers can cancel steel and other triggers, but hopefully it's still possible to prevent backroutes despite that.  I'll leave it for others to prove or refute that my idea can be made backroute-proof.

==============================

So the remaining issue is the fact that in order for all this to work, my setup requires precise control over where each lemming enters the level from.  This is a far cry from the usual way lemmings enter a level, namely as a stream coming from a limited number of entrances.  So I can understand objections around the "one entrance per lemming" requirement.

I'll have to think more to see if it's possible to remove that requirement and still keep the proposed scheme.  In past level design challenges, we have come up with ways to force a single stream of lemmings be split into multiple streams, so there's a chance that you can perhaps force the splitting of a stream of N lemmings to have each lemming end up going a separate path, which would then likely achieve the same thing as having one entrance per lemming.  But much work remains to be done to adapt my scheme to a fixed number of entrances.  It may be that with fixed number of entrances, it is easier instead to come up from scratch with a totally difference scheme for achieving NP-Completeness.  Consider that the sequel to geoo's problem of NP-Complete lemmings.

[chaos_defrost]

Hahaha, this is awesome. Happy birthday, prove Lemmings can be made NP-complete given certain criteria 

Thanks a lot, everyone. 

[Clam]

wow, what the...

... or, you could just build him a Highland level. Whatever floats your lemming-kayak, I guess.

[ccexplore]

Haha, don't look at me, geoo started it.

Incidentally, in terms of NP-Complete, I'm starting to wonder if my reduction of partition problem to lemmings solver is truly polynomial, or whether lemmings solver is in fact itself NP (can a given solution be verified in P?  How exactly are we counting size of inputs here?).  Eh, technical details...

[ccexplore]

As it turned out, after more careful reading of the partition problem, my attempt above in fact fails to properly prove NP-hardness.  The issue is that in the partition problem, size is measured both in the number of elements, as well as the number of bits required to represent all the elements.  I totally forgot to account for the latter.

If we want to make lemmings solver an NP problem to start with, we must take both the number of lemmings in the level, as well as the level time limit, to be part of the size of the problem, so that a lemming solution verifier can operate in P (ie. replay the solution up to the time limit, iterating through all non-dead lemmings on each frame update).  However, in my attempted scheme to convert Partition to a lemmings level, my scheme requires 2xS lemmings where S is the target partition sum.  Whereas we measure the partition problem's size as bits required to represent all elements, in other words O(log S) I believe.  So my proposed scheme is in fact an exponential rather than polynomial reduction of the partition problem to a lemmings level.

So oh well.  Maybe I will make a custom level instead after all.

[geoo]

What started out as an not really serious question, actually turned into a pretty interesting problem. It's also got more in common with the design game than I first expected, having had a try at it myself now.

Yeah, I just realized as well that set partitioning doesn't work here. If you encode the numbers in unary, the problem is not NP-complete, because you can just use dynamic programming to solve it in polynomial time; and if you encode it in binary, then the amount of terrain pieces you use for the partition primitive is exponential in the length of the numbers in binary.

I still liked that the idea you used to design that primitive, I think it could also be used as the unit primitive, if you sacrifice half of the lemmings of each unit by default (overall 25% to save then); it doesn't require to compress the lemmings.

However I think I found a way to reduce an instance of SAT (more precisely for expressions in conjunctive normal form) to Lemmings in polynomial time, and incidentally I need the unit primitive for it as well. However I can't use blockers in the setup, so I need a different setup for it. Also, it can easily be adapted to use only one exit, and I got an idea to use only one entrance as well (I didn't think about that actually when I first wrote up the challenge).

Here's a sketchy description of the scheme, an example level for L++ is attached:
For each literal you got one entrance, from which the lemmings drop into a 'unit' (by ccexplore's earlier description), essentially forcing the entire group to go path A or path B. Path A (the lower one) corresponds to the literal being assigned the value true, path B the value false.
In the example level, the 'unit' isn't quite working yet, as you can use diggers to desynch the lemmings in a 'unit' thus splitting up the group. However, in DOS physics that 'unit' would have to be adapted anyway, and I'm pretty sure something could be come up with (preferably something without compression required, I might try to think something up for it).
Then for each literal and each negated literal, there's a path consisting of M slopes where M is the number of clauses in the conjunctive normal form. If that literal appears in the Nth clause, there's opportunity to dig after the Nth slope to turn a lemming around onto a path to a 'box' corresponding to the clause. If it doesn't appear, then there's no such oportunity.
So, once you choose whether to pick the literal or its negation, you can send a lemming to every 'box' that contains that literal (or its negation respectively). If you manage to get at least one lemming into each 'box', then all clauses can be fulfilled. So it must be ensured that for each 'box', exactly one lemming can be saved (this is achieved using a 1px wide wall to dig to get around the splat distance for that digger).
The requirement of lemmings to save is the amount of clauses, which is achievable iff you get a lemming into each of the 'boxes' for each clause, i.e. fulfilling every clause and subsequently the entire expression. For each entrance, an amount of M+1 lemmings is sufficient (you could also use the 1 plus the maximum over the number of clauses the literal appears in, and the number of clauses its negation appears in). Plus 1, because in my current setup a bomber is used for each entrance. The amount of diggers the same as for lemmings, plus M (for digging the 1px walls).

The example level shows the Lemmings instance for the SAT expression (a v b v -b)(-b v -a)(-a v b), where v denotes the logical OR, - denotes NOT, and between the clauses there's an implicit AND. The expression can be satisfied using either -a and b or -a and -b. So in the example level, in the lower pair of lanes (literal a) you pick the upper of the two, and for the upper pair is doesn't matter. You dig whenever you get the opportunity (above the flipped T shaped steel structure), and you'll get at least one lemming into every box.

sentr.txt is an idea how to split up a group from a single entrances into groups of sizes of ones choice. Of course, the structure on the left should be steel entirely, and the skillset for the rest of the level shouldn't allow backroutes to it. A problem with this approach is that the lemmings won't come up spaced perfectly evenly, but if the 'unit' primitive doesn't require compression, then this shouldn't be of an issue.

Quote

Hahaha, this is awesome. Happy birthday, prove Lemmings can be made NP-complete given certain criteria 

Thanks a lot, everyone. 

I hope you had an entertaining read, mostly courtesy of ccexplore.


Mod Edit: Restored attachments.

[ccexplore]

Wow, awesome!  Excellent work!

I don't have much to add to geoo's brilliant solution, except:

a) an accounting of input sizes to ensure the transformation is polynomial.  Not that it was ever in doubt, but good to double-check since that was what tripped me on my attempt.

b) A better implementation of the literal primitive (aka "unit"), such that compression is not required.  In doing so, I double the number of lemmings per primitive, in two distinct groups (eg. coming out of 2 entrances), such that exactly one group will be all killed while the other group all released.  Furthermore, you have a choice of which group to release, and different paths will be taken (and cannot be altered after the fact) by each group.  This is DOS-mechanics based (either CustLemm or DOSLem works).

I also made some changes to the "box" primitive which should ensure it really only allows one lemming to survive through it, by avoiding cases where (for example) another lemming survives by digging simultaneously with the digger in progress (rare but I think possible in DOS lemmings under specific setups).  Just in case.  (Again, DOS-based, either CustLemm or DOSLem works).

Both attached.  For the level, the left half is my improved "literal" implementation (minus the additional terrain to make one path end up "above" and the other path "below"), and the right half is my improved "box" implementation.  If my construction works as intended without any backroutes, you should not be able to save more than 6 lemmings:  1 from the "box" exit, and other 5 all going into the same exit on the "literal" side of the level.

[edit: modify level to add extra miners and diggers, to better test out possibilities of backroutes in real usages of the primitives]

Mod Edit: Restored attachments.

[geoo]

Nice finishing, your adaptions should make this really backroute-proof now (just got to make sure now that the steel in the slope-part is placed in a way that miners can't use it to turn themselves around).
Your new unit primitive is pretty nifty as well.

Just one minor note on your analysis (which doesn't affect the outcome at all): The exit platform requires an amount of terrain pieces in O(N), not O(1), because its length is linear in the amount of boxes and therefore clauses.

Actually, we always assumed that Lemmings is in NP along the way, however we've just shown that Lemmings is NP-hard. In fact, I think this only applies if the time limit is encoded in unary, or if it is polynomially bounded in the level size (As assumed by this paper, which presents an alternative proof that I've only skimmed over yet: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.92.8338&rep=rep1&type=pdf It's also got a section proving this for levels containing only 1 lemmings, which might be another interesting challenge.)

I think that there are levels to which any successful solution takes time exponential in the input size. Here's a sketch of my idea: Have N lemmings, each starting on a platform (with borders left and right) which provides a walking distance of the length of the Nth prime P(N). Lemmings will walk back an forth on it, with each cycle taking 2*P(N) frames. Now, any successful solution needs all lemmings to be synchronized by the x-position (or requiring them to have a certain constellation, or something like that). Picking the right start positions, this can be made to require a time in frames equalling the product of the first N primes. As (N*log P(N))/P(N) converges to 1 as N tends to infinity, we can estimate N as P(N)/log P(N) for large P(N).
Our horizontal size of the level is in O(P(N)) obviously, and with that estimate the vertical size is in O(P(N)/log P(N)), so the overall size is in O(P(N)^2/log P(N)) =: M
However, the time taken to solve the level has a lower bound of 2^N (2 is a lower bound for each P(N)). Now N is super-logarithmic in M because log M = log (P(N)^2/log P(N)) = 2*log P(N) - log log P(N) = o(P(N)/log P(N)), and thus 2^N (the time taken) is super-polynomial in M (the level size).

For the actual implementation of this idea, perhaps nuke trick could be applied, where each lemming has to have a certain relative position to the previous lemming that gets nuked, in order to trigger a chain reaction that will allow the last lemming in the chain to enter the exit. I haven't thought up anything specific yet though.

[ccexplore]

Actually, we always assumed that Lemmings is in NP along the way, however we've just shown that Lemmings is NP-hard. In fact, I think this only applies if the time limit is encoded in unary, or if it is polynomially bounded in the level size

As soon I started to think about input sizes during previous postings, I already realized that you most likely have to count time limit (and number of lemmings) in unary:

If we want to make lemmings solver an NP problem to start with, we must take both the number of lemmings in the level, as well as the level time limit, to be part of the size of the problem, so that a lemming solution verifier can operate in P (ie. replay the solution up to the time limit, iterating through all non-dead lemmings on each frame update).

=====================

You exponential-time level idea do sound promising, I might give it a try and see if I can make it work.

[geoo]

I think we don't have to encode the amount of Lemmings in unary, because if we assume that each frame at most 1 lemming gets released into the level, the amount of lemmings in the play field is bounded against the time in frames it can take at most to solve the level. So having a polynomially bounded time limit (or a guarantee that a level can take at most polynomial time in its size, which we're just about to debunk though) in frames implies a polynomial amount of lemmings to consider. Even if we allow multiple lemmings to appear on the field in the same frame, instead of processing a step for each single lemming every frame, we can store for each position in the level and for each respective lemming state (e.g. direction, skill performed, animation frame, floater/climber, bomb timer) the amount of lemmings at that position in that state, where the amount of states is constant (determined by the game). Then processing one frame takes only polynomial time, even if we can assign multiple skills per frame, because for each (position, state) group a skill assignment action only takes constant time (group can only be divided into at most 9 groups, 1 for each skill type and 1 for doing nothing, and you only have to pick how to divide up that group into new ones, and add the size of each group to the amount of lemmings that are already in the (position, state) entry that the group gets transformed into).
One tiny issue might be if we have to establish an ordering on the lemmings (e.g. for selection priority or nuke), but as there's only a polynomial amount of groups per entrance (meaning lemmings that come out at the same frame), we can consider the entire group equivalent and just assign them the frame number they entered as priority value, and extend the (position, state) pair into a (position, state, priority) tuple which there's still only polynomially many of.

[ccexplore]

Interesting.  Another way ordering matters with DOS-like game mechanics is that the lemmings are processed in a strict order, and the terrain additions/removals of one lemming is immediately visible to subsequent lemmings even inside the processing of a frame update.  If I understood you correctly, you got around this for nuking by stipulating that if 2 lemmings entered the level at the same frame, they will start their nuke countdown at the same frame also.  We can do that too for general frame updates, stipulating that the 2 lemmings cannot see each other's terrain effects within the processing of the frame update (ie. they both only see the terrain the way it was before the frame update started).  However, in doing so, we now introduce a new issue:  what if one lemming is adding terrain to a pixel while the other lemming is removing terrain at the exact same pixel?  Does the pixel end up with or without terrain after the frame update?  It's not hard to resolve this issue, but it does add some new rules to the game mechanics that aren't needed when there's a strict processing order.

Still, if we simply stick with DOS game mechanics, you are absolutely right that, with only at most 1 lemming entering the level per frame, and at most 1 skill assignment per frame, both the number of lemmings and number of skills are effectively bounded by O(time limit).

[ccexplore]

I haven't forgotten about exponential-time level, but probably don't have time at the moment to create an actual level to illustrate.  I do have a pretty concrete idea though of how to create a level involving nuking that has the "chain reaction" setup geoo talks about, though it does make use of some particulars of DOS game mechanics.   I'll attempt to verbally describe below:

The basic construction looks something like this (note: distances shown are not accurate at all, this is just to show the general look):

         X      X
         XXXXXXXX
X     X
XXXXXXX
         X    X
         XXXXXX
  X   X
  XXXXX
         X  X
         XXXX
    X X
    XXX

A sequence of platforms alternating left and right, with exactly 1 lemming per platform walking back and forth on it.  Length of each platform follows the description geoo gave (eg. N-th prime etc.).  The walls and walkway of each platform are all exactly 1 pixel thick.

We will take advantage of the following details of DOS (DOSLemm or CustLemm) game mechanics:

A) if lemming is on top of a pixel inside a steel area, his explosion takes out nothing, otherwise it takes out the entirety of the usual area, including any pixels that are inside a steel area.

B) when a lemming transitions from walker to faller, he will move down exactly 4 pixels for that initial fall.  This fits well with the minimum size of 4 pixels for height of steel area.

C) falling lemming explode immediately when countdown reaches 0, without the "oh-no" part

The general idea is to make it so that, given a left platform (A), the next right platform (B) above the left platform, and then the next left platform above (C), we are enforcing a chain reaction by making A fall and explode in a particular way to free B, which then falls and explodes in a particular way to free C, and so forth.  Specifically:

i) each walkway is protected by steel area, but the steel area is only 4 pixels tall.  So a lemming standing/walking on the walkway will take out nothing when exploded, but as soon as they can be made to fall off the walkway, their explosion will then take out terrain.  That's because their initial fall of 4 pixels will ensure that they are off the steel area, even with the alignment and size restrictions for positioning of steel area in DOS mechanics.

ii) we arrange the horizontal distance between the right end of A, and the left end of B, in a particular way, as well as the vertical distance between A and B.  Namely, we want it so that the lemming from A must fall off at the right, from the very edge of platform A (ie. upon falling, lemming is at the column of pixels making up the right wall of A), and must explode right after the initial 4-pixel fall, to take out just enough pixels to allow B to perform a corresponding fall.  If A doesn't fall, then his explosion has no effect due to the steel on the walkway.  If A falls past the initial 4-pixel fall, then he is too low for his explosion to take out any pixels of platform B.  If A is falling not from the very edge of platform A, then the explosion doesn't reach to the right far enough to take out any pixels of platform B.

It's not hard to see that with this arrangement, it's also not possible for lemming A to directly free lemming C (B is already barely low enough for A to affect, so C at roughly twice the vertical distance is simply too high).

I hope this is descriptive enough for you to see the chain reaction, and how each lemming has to be at a very particular, pixel-precise location to trigger the next lemming in the chain.

What's left is a lemming to start off the chain reaction (ie. someone below the lowest platform, whose explosion will allow the lowest-platform lemming to fall and start the chain), as well as some way to allow the last lemming in the chain to either get himself or another lemming to reach the exit.
 

I've also read through the paper geoo referenced that has the 1-lemming construction for NP-hardness.  Interestingly, in that paper they resorted to asserting that the time limit is polynomially bounded by the level size, and conjectured that it is so (but no proof or even the slightest justification attempt), in contradiction to geoo's N-th prime construction.  On the other hand, we resorted to nuking to make geoo's exponential-time construction work.  So naturally the question is, if we are not allowing solutions involving nuking, is it still possible to come up with a scheme where required time limit is exponential to level size, or does it become polynomial then?  Note that with nuking, you have a move that is applied one-time only and affects all lemmings at once.  This is quite different from your usual skill assignments, which affects only 1 lemming at a time, and which you have nearly full control of timing of when to assign.

[ccexplore]

So naturally the question is, if we are not allowing solutions involving nuking, is it still possible to come up with a scheme where required time limit is exponential to level size, or does it become polynomial then?  Note that with nuking, you have a move that is applied one-time only and affects all lemmings at once.  This is quite different from your usual skill assignments, which affects only 1 lemming at a time, and which you have nearly full control of timing of when to assign.

I thought about it a little more, and I think I can modify my chain reaction scheme above so that instead of nuking, you assign exploders explicitly, but the timing requirement is still such that everyone needs to be at the right place (in order to enforce the "product of N primes" aspect).  At least that's my hope, please read this over and see if you spot a hole in this approach.

(I'm not going to bother with spoiler tags, I don't think they are necessary for the very limited audience of this thread. )

[edit: clarified description in certain places]

--------------

This time the chain reaction goes downwards instead of upwards, and instead of alternating platforms, you simply have a series of platforms from top to bottom, each slightly offset to the left from the previous platform above.  For those who haven't read the description of the nuke chain reaction, each "platform" is simply 1 one-pixel thin horizontal walkway with 1-pixel thin walls at each end, with exactly one lemming walking back and forth per platform.  In other words, the general shape of the platform is:

X   X
XXXXX

At the top, you can explode one lemming to release another, causing it to fall down.  However, that lemming needs to be released just before he turns around at the right end of the platform he is walking at, so that when he starts falling he is doing so at the column of pixels of the wall at the right end.  If he falls anywhere else, his fall will be cut short by splatting on some terrain below.  (Terrain which is still well above the walkway of the next lemming in the chain.)  Because the exploder simultaneously take out a bunch of pixels, in the case where he is nowhere near the explosion area when the explosion occurs, he will still not be able to subsequently reach where he is required to start falling, due to the gap form by the explosion on the walkway.

If you successfully allow that lemming to start falling at the right place, he will still end up splatting, but at a much lower position then if he started falling at the wrong place.  This gives him a chance to reach the next "link" in the chain, but doesn't give him so much time that you can wait for the next lemming in the chain to get to the right place.

Now we need to enforce that the falling explosion happens only at a particular desired position.  We will do so as follows.  First, note that the bottom-left portion of the explosion mask looks something like this:

+++++++
 ++++++
  +++++
    +++

So there are 3 cases:  exploded too early in the fall, just right, or too late.

Too early (| is column of pixels for wall):

+++++++
 ++++++
  +++++
XXX|+++
    ^

The lemming ends up falling at location marked ^, just one pixel horizontally past where the wall at the right end of the platform is located.  He will splat prematurely if he falls at that position.

Just right (recall that each frame of falling changes y by 3):

XXX|+++
 ++++++
  +++++
    +++
  ^* 

Obviously the "xxx|" will be taken out by the explosion as well, I just leave them in there to show the relative position of the explosion mask to the platform.  In this case, the to-be-released lemming must be standing horizontally at column of pixels marked by ^ when the explosion happens, in order to fall at *.  Otherwise if he doesn't fall at *, he splats prematurely during the fall.  If he is nowhere near the explosion area, then he is simply unable to reach ^ and fall at * subsequently, since the explosion takes out more pixels to the left than that.  And if you are sneaky and try to make the lemming "oh-no" while standing at * so he does fall there, well, there's only a limited (and fixed) amount of time before "oh-no" explodes, and that amount of time is too short for the released lemming to fall to where he needs to be for next part of the chain.

Finally, if even one frame too late, then the exploding faller lemming splats before he can explode, failing to release the next lemming in the chain.  If I recall correctly, splatting will cancel an impending explosion.  If not, I'm sure you can do something with traps or steel areas to make sure the lemming can never explode below the "just right" point.

So in summary:

1) Each lemming falls and explodes to release the subsequent lemming in the chain.

2) When you release a lemming via explosion to make him start falling, there is only a finite amount of time before he splats, no matter where he is falling at.  So you can't wait indefinitely for the next lemming in the chain to be at the right place.

3) when you release a lemming via explosion to make him start falling, if he is not falling at the exact correct x position, he splats prematurely before reaching the next part of the chain, thus stopping the chain reaction.

4) There is only one correct x-position the next lemming in the chain should be at, before he gets released.  If he is at the wrong x-position within the explosion area during release, he falls at the wrong x-position and splats prematurely ending the chain.  If he is nowhere near the explosion area, he can't subsequently reach the right x-position to fall.

5) The falling lemming has to explode at precisely the right time.  If he explodes too early, either he is too high to take out any terrain of the next part of the chain, or even if he is high enough, he doesn't take out the pixels needed to allow the next lemming in the chain to fall at the right place, instead causing the next lemming to fall one more pixel to the right of the correct falling position, resulting in eventual splat and premature end to chain.  He can't explode too late because one frame past "just right", and he splats (or otherwise gets killed immediately in some fashion) instead of exploding.  Only at the "just right" position will he take out all the terrain pixels that needs to be taken out for the next lemming to have a chance at continuing the chain.

6) It should also be easy to ensure a nuking solution won't work (or won't help much).  When you nuke each lemming explodes one after another (more or less), we can simply ensure that the falling to next part of the chain takes too long for a nuking solution--the next lemming in the chain explodes himself before the previous lemming is able to release him via explosion.

-----------------------

The one aspect I'm not confident on (and perhaps this applies to the nuking version as well, I don't know) is that there's a bit of delay going from one part of the chain to the next, due to the falling (which has to be high enough to accomodate the various splatting required to enforce the chain).  That delay should be constant however at each "link" of the chain, and I'm hoping that is enough to ensure that mathematically you can still create the product of N prime condition, instead of having some other earlier timing that also happens to work out.

If anyone actually wants to create a level based on my description, you'll probably need L++, since the limited vertical span of DOS levels may make it impossible to create a meaningful version in Lemmix/LemEdit.  On the other hand, some aspects of my solution are based on details of DOS game mechanics, and may need to be modified to carry over to L++.  Hopefully it still works in L++ mechanics!

[geoo]

Ah, your second realization of the idea looks very clean, and I think it should also work in L++ and other physics. Nice! Hahaha, we should make and release this level for the Clones site!
So this conclusively proves that polynomially bounded levels can still take exponential time to solve, contrary to the conjecture in the paper.

However, this doesn't prove that Lemmings as we defined it isn't in NP: A friend of mine suggested that our solution verifier could, if there's only polynomially many moves to the solution, simulate it as follows in poly: Assuming that the terrain doesn't change unless a skill is assigned (whose completion will only take polynomial time; that doesn't take into account e.g. bashers caught between blockers, but they don't change the terrain after more than a poly amount of time either), the terrain in the level doesn't change, and thus lemmings will walk in a cycle, and not affect each other (I just realized that the latter assumption is precarious, because you might set up an exponential bunch of lemmings and a polynomial amount of traps in a very clever way that it's difficult to simulate the behaviour). Then you could detect the cycle length (which is poly as the level size is poly), and calculate ahead where the lemming will be at the point in time the next move is performed.
Of course, this doesn't automatically prove that these levels could still be simulated in poly time, as you could try a setup with exponential skills, or some trap setup like I insinuated, but then again you could adapt the solver for these special cases as well. Therefore I think it's generally hard to prove that Lemmings is not in NP (if that is even right), as the problem (find a solution format that describes every solution in a way that it takes poly space and can be verified in poly time) reminds me a lot of Kolmogorov complexity, which is uncomputable. In the same way, should the problem be in NP, I think it'd be very difficult to provide such a format, having to consider all kind of things, unless some useful abstraction can be found.

Interesting.  Another way ordering matters with DOS-like game mechanics is that the lemmings are processed in a strict order, and the terrain additions/removals of one lemming is immediately visible to subsequent lemmings even inside the processing of a frame update.  If I understood you correctly, you got around this for nuking by stipulating that if 2 lemmings entered the level at the same frame, they will start their nuke countdown at the same frame also.  We can do that too for general frame updates, stipulating that the 2 lemmings cannot see each other's terrain effects within the processing of the frame update (ie. they both only see the terrain the way it was before the frame update started).  However, in doing so, we now introduce a new issue:  what if one lemming is adding terrain to a pixel while the other lemming is removing terrain at the exact same pixel?  Does the pixel end up with or without terrain after the frame update?  It's not hard to resolve this issue, but it does add some new rules to the game mechanics that aren't needed when there's a strict processing order.

I was thinking of just picking a bunch of lemmings from the equivalence class to get assigned the skill, and taking the ordering within the class just as it fits our needs, to establish a strict ordering, but I'm not quite sure whether that'd actually work, because could it be if we do this twice to a group with the same priority (e.g. split it up and reunite it), that our priority choices could be contradictory? I'm trying to wrap my head around this idea to setup such a scenario, but it's kinda confusing, and I'm also not that intimate with the precise happenings between two lemmings that affect each other during the same frame (e.g. does a lemming that is dug under by another lemming that gets processed earlier transform into a faller right in that frame, or only the next frame and could thus still be assigned a builder?).

[ccexplore]

I'm trying to wrap my head around this idea to setup such a scenario, but it's kinda confusing, and I'm also not that intimate with the precise happenings between two lemmings that affect each other during the same frame (e.g. does a lemming that is dug under by another lemming that gets processed earlier transform into a faller right in that frame, or only the next frame and could thus still be assigned a builder?).

The former, under DOS game mechanics.  The changes in terrain by the earlier-processed lemming are fully visible to the later-processed lemmings.  If the ordering is switched so that the digger is processed later, then the earlier lemming doesn't see the effect of the later digger until next frame update, and therefore you can still assign builder.

[viglietta]

Hi, I recently wrote a paper discussing the computational complexity of Lemmings.  Inicidentally, it answers the questions you were asking in this thread.
http://www.di.unipi.it/~vigliett/files/papers/lemmings.pdf

Regards.

P.S.  I would greatly appreciate your comments and corrections, especially concerning my description of the game mechanics (Section 2).
P.P.S.  The PSPACE-completeness proof in my paper builds upon another result of mine, contained in this other paper:
http://www.di.unipi.it/~vigliett/files/papers/gaming.pdf

[geoo]

Very nice work! Yeah, we got the NP-hardness and existence of exponential time solutions independently here in the forum, but not the question regarding PSPACE-completeness. I was perhaps going to look into it at some point, but it seems that you beat me to it.
And have fun at Fun with Algorithms.

I read through your papers, and the results and proofs seem sound to me, except for some details related to peculiarities in the mechanics. But well, that's what you get for not using a simplified model like Cormode and Forisek did, right?
Also one thing I noticed is that you restricted the amount of Lemmings to be polynomial (which I think is reasonable), while Cormode sneakily got around encoding values in unary by just encoding each Lemming's start position individually. If we're on about entrances already, DOS lemmings also has some quirks in this regard, not always spawning them cyclically, but if there's two entrances it uses the order ABBA, and if there's three, the order ABCB.

Oh, and I think the link to the Lemmings wiki in your references is dead by now, didn't notice it got taken down until now.


Anyway, I'm not sure how strictly you want to adhere to the original physics, but I'll describe some things that require revisions in some parts if you want to take these quirks into account:

First off, it is possible to assign miners and bashers turning them around without removing any terrain. The first two levels in the attached level pack display that: If you assign a basher at the right time shortly before the gap, or a miner before the small pit, they will turn around without removing terrain.
This makes Lemma 1 wrong (assuming you mean an encoding of all actions as the size of a solution, without any compression): For instance, you can design a level using synchronization (prime sized platforms like described in this thread or by Forisek), placing steel in such a way that it's impossible to bash for delay. Have e.g. the smallest of the platforms require to use the basher trick/glitch shown in my attached level to have the lemming stay on the platform. It takes exponential time to synchronize all lemmings, and the one on the smallest platform will have to do exponentially many basher strokes.
Of course, this basher's action will be periodic as well, and so you can predict it as well without having to simulate every single step, so Theorem 1 still holds, with some adjustments to the proof.

In this section there's another statement that isn't quite accurate (page 7, 3rd paragraph): "In order to offset l's phase within its own period by any desired amount, just polynomially many Basher skills are sufficient, and may be assigned at any time."
Perhaps I'm a bit nit-picky here, but any desired amount might not be possible, because the greatest common divisor of the cycle length and the offset gained from bashing once might not be 1. You can't assign them at an arbitrary point either, but have to do it at some point where bashing has no effect. It should be noted that the offset by bashing is not necessarily constant due to the behavior of the basher turning without removing terrain as described above, but in any case it should be possible to achieve the offset that was achieved in the original solution using only O(cycle length) bashers (in addition to those that might be applied periodically, as described in the previous paragraph).

Another quirk that has some effect on your construction for the PSPACE-completeness proof is that in the original game, trigger areas overwrite steel (and blockers overwrite both until removed, but that's a different story). You can check this out in your level showing off the path gadget, allowing to turn around. This should have no effect or at least be easily amended, and shouldn't affect the end result.

The third level in the attached pack shows another quirk, namely that builders are asymmetric depending in which direction you build. I don't think this has any effect though, as you don't need to mirror your gadgets.


Then a few more general notes on Lemmings physics as described in Section 2:

You describe the assignment priority in Lemmings, but then never reference it again. I think it's ok not taking it into account, as it just makes proofs more technical if you want to be sure not to run into issues with it. Also, if there's a worker lemming (builder, basher, etc) under the cursor and a walker, then the worker will get the assignment priority (even if the worker is "younger"), unless you hold the right mouse button while clicking.

Describing a blocker as acting like a wall might be a bit misleading. It only acts somewhat like a wall to walkers walking against it, while fallers can fall into the blocker just fine (i.e. without landing on something like a wall), and blockers also turn builders, miners, fallers, etc. around, which walls don't.

And finally, the basher check. It's pretty weird, I'm just gonna ccexplore on this one (hope he doesn't mind):

It checks 4 pixels, and yes, 6 px above ground.  More precisely, for DOS Lemmings anyway (details for Amiga/SNES etc are likely similar) when basher is at (x,y) [location being the pixel he's actually standing on] it will check pixels (x+8, y-6) thru (x+11, y-6) [analogously if facing left].to be all empty to stop bashing.  This check is done only on every other stroke starting with the first.

I'm not exactly sure when or how the steel check occurs though.

[viglietta]

Wow, you are certainly an expert in Lemmings and the related literature.   
Thanks for taking the time to write such a comprehensive comment, I sincerely appreciate your effort!

I was aware that I was omitting some details of the game mechanics: I did it due to space limitations (12 pages), and only if they didn't matter for the later proofs.  The only thing that I really need for the NPO part is that the configuration transition between time units can be computed in polynomial time, which is abuntantly true regardless of the details.  On the other hand, I describe Builders and Bashers as thoroughly as I can, because I am going to need them for the PSPACE-completeness part.

However, I was unaware of many aspects of the game that you pointed out, mainly because I tried to figure them out by experimentation and trial and error.  So your contribution is extremely helpful there.  I also wonder if there is any standard "tool" to discover such things, because right now I am only using the game itself and the Lemmix editor, but I have a hard time pausing the game after each frame, for instance...

Luckily enough, most of my misconceptions don't seem to substantially affect the paper's main results.  I also extensively tested all my gadgets, and they all seemed to work even when I tried my best to "break" them (making such a "robust" Door gadget took me quite a lot of time, actually...).

I will take into account all your comments, and see where I have to correct the paper.  Hopefully I can keep it within 12 pages, which is my main concern right now...

Cheers!   

P.S.  The Lemmings Wiki was there just a couple of days ago, when I last checked!  Maybe it's just temporarily offline?  Can some admin confirm this?

[Simon]

Yep, you already did extensive trial-and-error on the physics.

Your notion of time interval seems to be equal to two game updates, not just one. This seems somewhat random, but if you use it consistently, it's perfectly fine.

I wrote an essay about the location behavior of the pin for walkers (I called the pin "effective coordinate"). Most notably, the pin isn't symmetric for left/right walkers.

Since you describe builders extensively: The placement of a builder's brick has been amended to look nice with the sprite. Since the pin isn't symmetrical w.r.t the sprite, the brick isn't placed symmetrically w.r.t. the pin either. In bridges built by a right-facing builder, the pin on brick-placement is in the leftmost pixel of the brick. In bridges built by a left-facing builder, the pin on brick-placement is in the second-to-rightmost pixel of the brick.

As a result, if the player waits as long as possible before re-assinging builder, bridges going to the right can be stretched further (with a 1-pixel overlap) than bridges going to the left (with a 2-pixel overlap). Immediately re-assigning builder would make a 4-pixel overlap in both directions.

You already say "the pin depends on direction", so maybe you don't have to alter much, if even anything, to have the paper acceptably accurate. This is just an ugly result of sprite placement, and making the physics look nice with the sprites.

Good luck with the thesis!

-- Simon

[viglietta]

Thanks a lot, Simon!

Yes, I read your essay before writing the paper, and it helped me a whole lot!  I briefly took care of that asymmetry by saying that the pin position depends on direction, and that is kind of sufficient for the scope of the paper.  The main issue here is the space constraint of 12 pages!  I would love to add more details, but I don't know how to fit them all.

By the way, I'm not really doing this for my thesis, it's just for fun!  But thanks anyway.   

[ccexplore]

By the way, I'm not really doing this for my thesis, it's just for fun!  But thanks anyway.   

"just for fun"?  Oh, how I envy you guys with seemingly unlimited free time, something in short supply when one has to work for a living.

Cool paper though, I haven't had a chance to read in detail but it was intriguing just from the abstract.

Regarding glitches, keep in mind that Lemmings is possibly one of the most ported games in existence, with a version available in almost every PC or console system you can think of.  I don't know (as I haven't read through your paper yet) if the scope of your paper is specifically geared towards DOS Lemmings (which is what Lemmix emulates) vs some other version, but given that there's bound to be some obscure behavior unique to each particular version, I don't think it'd be necessary to be absolutely complete in terms of the game mechanics.  I suspect none of the differences would've affected your results anyhow.

[ccexplore]

I just got some reading done and got to page 2.   Okay, maybe not as much reading as I'd like.

The "deadly zone" definition was interesting as an attempt to merge water/lava type objects and triggered-trap objects under the same definition, but as a result it's not quite accurate, or at least somewhat ambiguous the way I read it.  The key difference is that if you have multiple ("N") lemmings moving perfectly in sync with each other (ie. they are all compressed to the exact same position and moving together), and then they reach the object's trigger area, a water/lava type object will kill all of them at once.  A triggered trap will only affect 1 of the N lemmings.  Whereas in your definition, it reads more like all N of the perfectly-sync'ed lemmings will all get killed as they all move into a triggered (ie. k > 0) trap, and then the trap becomes inactive for the next k time units.

I suppose with a more fine-grained definition of time unit that considers the update of each individual lemming to occur at distinct time units, your given definition would be accurate, although I think it would also allow triggered trap objects that don't actually exist in the real game.

Anyhow, I'm sure it doesn't really affect the results of the paper in any meaningful way.   I guess I'll read on and find out.