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).