A bit late to the party, but this question keeps bugging me due to the inefficiencies of the solutions I read... many of the other answers focus on proof of existence. This answer focuses on running time.
I predict that a complete algorithm including the following as its core will have a worst case running time less than of 4.875 * 2^N in the limit for any value of N for which it is meaningful (and probably all values of N - not yet proven). In Big-O notation, that's O(2^N), so not merely polynomial in the exponential, but possibly constant. The exact limit for the presumed worst case for N >= 3 is 4.875 * 2^N - 2(N+1)^2
The core function in the protocol, and the only one used to control the lights is where a given set (or a subset of a given set who have made a specific observation) announce themselves to "all other prisoners". Each message has a well-defined maximum number of recipients, and lasts for this many days (and not a single day more!). It is not guaranteed that all senders of a message will receive it back, but that is fine, because the senders already have the information being sent.
As with other solutions, the first phase is to establish upper and lower bounds for N. This procedure guarantees to complete in 2^N - 1 days, and not a single day more.
During this phase, we also partition the prisoners into K groups where K <= N <= 2^K, based on which round each prisoner discovered a minimum bound for N.
Before starting, a single set is defined consisting of "you". This will be referred to as s0 from here on. On each round at least one further set is defined consisting of at least one other prisoner, until there are no more prisoners, at which point everyone is aware of this.
Phase 1, round J (1 <= J <= K) lasts for 2^(J-1) days.
Everyone who is not in a numbered set turns on their light.
Everyone takes note of what they saw on the first day of the round.
For those already in a numbered set, this will be communicated to everyone else in phase 2.
For those who are NOT in a numbered set, anyone who did not see a light notes that they are in a member of sJ.
For the remainder of the round (for round 1, this does not happen, as it only lasts a single day), the message is repeated (including being relayed by anyone who saw a light the previous day) until everyone will necessarily have received it. On each day, at least one person who did not see a light the day before will see a light today.
By the last day of the round, either everyone is aware of the existence of a non-empty sJ (everyone sees a light, except a maximum of one person who was already setting their light on day 1 of this round).
If sJ was non-empty, we proceed to the next round of phase 1, taking twice as many days.
If sJ was empty, all prisoners have now been allocated to a set, so we proceed to phase 2 immediately.
Phase 1 lasted for K round taking in total 2^K - 1 days, where K <= N <= 2^(K-1)
At the end of phase 1, the following common knowledge is known by ALL prisoners:
- the value of K
- s0 has precisely 1 member.
- an upper bound on the number of members of sJ (1 <= J <= K) as 2^(J-1)
- the protocol that will be followed going forwards, and in particular
- a rule that the number of members of sJ cannot be more than the total of sI for 0 <= I < J.
Each round J of phase 2, 1 < J < K establishes common knowledge about the size of sJ that was created during phase 1 round J.
Phase 2 round 1 lasts for zero days, and only involves "you".
If "you" failed to see a light on day 1. s1 is empty, and you are the only prisoner.
If "you" saw a light, you already know that s1 is non-empty, and so does everyone else.
Phase 2 round 2
This uses a different message to the later rounds, as only 1 bit of information is required to determine whether s2 has 1 or 2 members.
If s2 has only 1 member, then whichever of s0 and s1 failed to observe a light on phase 1, round 2, day 1 (overall day 2) sends a message by setting their light.
This message must be repeated for at least N-1 days. We do not yet know N, but if this message is sent, it will be because s2 has only 1 member, which in turn means that s3 can only have a maximum of 3 members (rather than 4), s4 can only have a maximum of 6 members (rather than 8), etc...
In total, the message would reduce the upper bound of N that is common knowledge by 2^(K-3).
The number of days that s0 or s1 turn on their light for this round is thus 2^(K-1) - 2^(K-3) - 1 = 3 * 2^(K-3) - 1, by which time the message, if sent, will have reached all prisoners.
On receipt of the message, it becomes common knowledge the s2 has 1 member, and the commonly known upper limit is reduced permanently by 2^(K-3).
If the message is NOT received, the upper bound remains the same, but everyone now knows that s2 contains EXACTLY 2 members. Clearly the warden was feeling generous, as reduced the value of K, so that reaching this point (enumerating the first 4 members) has taken less than half the amount of time it could have taken.
Phase 2 round J (2 < J <= K)
The main purpose of this round is to define bounds on the size of sJ. If no earlier set has more than 2 members, these bounds will be established precisely.
Unlike round 2, or the rounds of phase 1, this will consist of multiple messages defined in the following order:
Each sI, 0 <= I < J, is given the opportunity in turn to send a message if they failed to observe a light on the first day of round J of phase 1.
The maximum time for the message to reach all members, if sent, will be [current upper bound for N] - 2^(K-J-1) - 1.
After waiting this many days everyone either:
- reduces the upper bound of the number of members in sJ by 1 (message received)
- increases the lower bound of the number of members in sJ by the number of members of sI (message not received). NB the first such "message not received" confirms the implicit lower bound of 1, so at the start of the round treat the lower bound as though it were zero.
This in turn causes the upper or lower bound of N to be updated. Reducing the upper bound is, of course, most useful to us. The common knowledge upper bound is reduced by 2^(K-J-1). Once again, the update, if it occurs, is immediate, and applies to the very next message.
It is not necessary to "ask" sJ or sI (I>J) if they saw a light on that day, as it is implicit in the definition of the set.
After each earlier set has sent (or not) a message, we check again the list of sets. If we received a message from that set, it indicates that at least one member of the set did not see a light, but for any sets with more than one member, we need to know whether they all saw the same thing.
Therefore for each such set where this is not immediately apparent, we wait for a further message indicating whether anyone in that group DID see a light on the relevant day. Receipt of this message does NOT reduce the upper bound for N, so unlike the other messages we wait for [current upper bound] - 1 days.
If this second message is received, or it was immediately obvious that the set could not all have had the same observation, the relevant set, sI is split into two sets, sI.0 and sI.1. For all further rounds of phase 2 (or phase 3 if required), they will be treated as two seperate sets. If the original set had at least 3 members, it will not be clear at this point how the original set was split, so we will need to clarify that in phase 3. It would be POSSIBLE (but unlikely if the warden was paying attention) that this could resolve itself later in phase 2 if one or more of the subgroups also get split.
The end of phase 2 occurs in round K. If phase 3 is not necessary, the final message, if sent, results in the common knowledge upper and lower bound for N becoming equal. However, the moment the prisoner who would be sending that message receives (or fails to receive) the penultimate message, that prisoner (and that prisoner alone) knows the true value of N for certain, and announces this; also setting the light in case the warden does not react by releasing all prisoners immediately.
It is assumed that the worst case occurs when K = N, i.e. when the warden has arranged that each of our sets contains precisely one person. In this case our initial estimate of N will be K^N
Running time of presumed worst case:
The presumed worst case is also the simplest for the warden to arrange - never move any prisoners.
In this case, each round in phase 1 creates a set containing only a single prisoner, taking 2^N - 1 days.
Phase 2 round 2 takes 3 * 2^(N-3) - 1 days, leaving a well known upper bound for N of 3 * 2^(N-3)
Phase 2 round J uses J messages which reduce the upper bound for the number of members of sJ from J to 1. During this time, the well-known upper bound for N is reduced as an iterative step from J * 2^(N-J) to (J+1) * 2^(N-J-1).
Observe that J * 2^(N-J) = 2J * 2^(N-J-1)
The first and second messages take (2J - 1) * 2^(N-J-1) - 1 days to transmit, and the remaining messages each an amount of time that is shorter by 2^(N-J-1) days, until the final message at (J+1) * 2^(N-J-1) - 1 days.
This gives a formula for days taken for all the messages in round J of
(J^2 + J(J+1)/2 - 1) * (2^(N-J-1)) - J
The very final message can be skipped when J = N - 1, saving N - 1 days that it would otherwise have taken to send that message.
This gives an overall formula for the total running time of (switching to lower case variables which wolframalpha understands!)
2^n-1 + 3 * 2^(n-3) -1 + sum_(j=3)^(n-1)((j^2 + j (j + 1)/2 - 1) 2^(n - j - 1) - j) - (n-1)
This simplifies to a surprisingly simple-looking formula:
39 * 2^(n - 3) - 2 (n + 1)^2
... or to put another way:
2^n * 4.875 - 2(n+1)^2
... which agrees with the output from a more detailed simulation I performed earlier.
Details of phase 3 need to be confirmed. Other answers already give techniques by which, given an upper bound on N, and a number of defined sets, we can force one of the sets to be split into two subsets in O(n^2 * [upper limit for N]) operations.
Note that in our initial construction, for any set containing more than 1 member, the value of K must be reduced by 1, halving our initial upper bound on N, and as such we reach the point where we know for certain that a set contains more than 1 member in a fraction of the time that we could have reached a similar point had those members been split into separate sets within phase 1.
It is not clear at this moment at what point it becomes more efficient to run a round of phase 3. For example, suppose we have least 10 prisoners arranged into 8 groups as follows (I'm working with a specific example using excel to save my head exploding!)
s0: 1, s1: 1, s2: 1, s3: 3, s4: 1, s5: 1, s6: 1, s7: 1
First, we know that the presumed worst case for 10 prisoners is 4750 days.
However, because we have only K groups, we start the algorithm with K = 8, and the first few stages of the analysis are the same as if N = 8.
The first difference occurs in phase 2 round 3, where rather than waiting 79 days for the first 2 messages and a further 63 days for the final message, we wait 79 days for all 3, and do not receive any of them (thus we know that s3 has 3 members). The upper bound on N then remains at its former value of 96, because none of these messages were received.
For round 4, we assume that the warden arranged prisoners so that the person who did see a light was in set s3, (otherwise we would successfully count the member of s4, as group 3 would have been unanimous in stating they did not see a light).
Therefore s0, s1 and s2 will all send messages saying they did not see a light, as will the other 2 members of s3. Those 4 messages take 87, 79, 71, 63 days respectively, leaving us with common knowledge that 10 <= N <= 64 (or generalising, K+2 <= N <= 2^(K-2). In fact K = N-2, so the lower bound on N has already been reduced to 2^(N-4).
It is immediately obvious that at least one of the members of s3 must have seen a light, as otherwise s4 would be empty, so we don't bother with a message to confirm that, instead we immediately split s3.
Common knowledge at this point will be:
s0: 1, s1: 1, s2: 1, s3.0 + s3.1: 3, s4: <=2, s5: <=8, s6: <=16, s7: <=32
Continuing another round of phase 2 allows the upper bound on s5 to be reduced. As s3 has been split into 2 separately-identifiable sets, we now get 6 messages in round 5 rather than the "normal" 5 messages. All but 1 of these will in fact indicate that the prisoners did not see a light, and the warden will surely not conveniently split s3.0 for us (which really conains 2 prisoners although we do not know this yet). These messages take 59 + 59 + 55 + 51 + 47 + 43 days to transmit, (314 days for round 5), resulting in common knowledge that includes the following:
s0: 1, s1: 1, s2: 1, s3.0 + s3.1: 3, s4: <=2, s5: <=3, s6: <=11, s7: <=22
In a similar manner, round 6 would have 7 messages totalling 257 days, and round 7 has 8 messages totalling 219 days, leaving a final state if phase 2 is run to completion of:
s0: 1, s1: 1, s2: 1, s3.0 + s3.1: 3, s4: <=2, s5: <=3, s6: <=5, s7: <=9
10 <= N <= 25
At this point, a total of 1677 days have elapsed in this specific example, giving 4750 - 1677 = 3073 days to run a phase 3 algorithm that forces one group to split and still beat the worst case for N=10. As our upper bound on N at this point is only 25, the maximum time to transmit a single message from one prisoner to all other prisoners is 24 (and other protocols may well include messages known to be sent by multiple prisoners, or which are not intended to reach all prisoners). This gives (at least in this specific case) a budget of at least 128 messages without exceeding the upper bound already established.
The improvement in running time decreases exponentially (in fact contrary to the day counting above, the warden needs to ensure that it is a group of uncertain size rather than s0 which confirms the lower bound of 1, so that buys a few irrelevant extra days).
If in fact N > 10, and the warden had "hidden" at least one extra prisoner in at least one of the later groups, the analysis so far would be the same, but as N is higher, we have even more time to run a "phase 3" protocol.
In this specific instance, what we would ideally want to do is have s3.0 send a 1 day message, and every set (including s3.0) send a message to indicate whether they received that message. This would reveal that s3.0 had 2 members, as 2 different sets must have received the message.
The final design of the phase 3 protocol would need to establish more precisely:
- how many more rounds of phase 2 we run before the diminishing effect of the reduction in upper limit makes it more efficient to run a round of the phase 3 protocol next.
- which messages are sent and in what order.
- whether we are in fact able to guarantee that phase 3 does not take more time than the presumed worst case for the same N (NB not the same K).
- whether we use "new" messages to force the size of the group to be revealed, or messages that we know were already sent earlier in the protocol.
Because that part is still not fully defined, the worst case is merely presumed, however, the intended elegance of the solution is that the warden cannot make phase 3 "complicated" without exponentially reducing the running time of phases 1 and 2.
Post-script - what about a practical running time?
Even with this relatively low worst case, the worst case running time even for relatively small values of N spirals out of control.
The above protocol could be modified so that (for example) if phase 1 round 7 indicates that there are still unallocated prisoners, we assume that the upper limit is (say) 128. Phase 1 rounds 8 to 128 would then be done in just 1 day each, as we no longer check for responses in order to modify the upper bound. Given that all other prisoners would then receive a work sheet with this fixed upper bound built in, they have no choice but to follow the protocol as written if they wish to have any chance of using it to escape alive.
If in fact N > 128, prisoners who still see a light at the end of round 128 would know that the protocol had failed and the procedure was doomed to failure. These prisoners, and any others who receive contradictory messages, should leave their lights off permanently to minimise the risk of the warden arranging for a prisoner to receive a false message.
The main additional change would be that K would be initially unknown, 8 <= K <= 128.
Otherwise, the protocol would work pretty much as-is, with 128 used in place of any upper bound of N that would otherwise be larger than 128, and possibly some additional messages used to probe whether a given set exists (the group itself, and anyone who saw a light on during the day of the group's creation could initially confirm this) once the existence or not of that group starts to have a significant effect on the upper bound in use.
For all values of N that are really up to 128, this will work correctly, and with the running time greatly reduced to human scales.
However, the because phase 1 gets reduced to a constant value for K >= 8, the disincentive for the warden to make "complicated" cases that need lots of work to resolve in phase 3 is greatly diminished even for N <= 128.
Although the warden can interfere with which messages are received by at least one prisoner if N > 128, so that prisoners get out of synchronisation with the protocol, it will still take multiple years before anyone makes a false declaration (for example declaring that N = 8, when in fact it is higher, having been tricked into believing the common knowledge is different to what it really is). It is hoped that this gives the rebel alliance's special forces unit time to overthrow the evil dictator!
However, that latter case is kind-of cheating, and there are possibly more efficient protocols that can be used if we're assuming a fixed upper bound anyway.