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
XXXXXAt 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!