The shortest sequence of bits that deterministically reveal the full state of a pseudo-random number generator

A pseudo-random number generator (PRNG) is a deterministic object, with a finite internal state, usually initialized by some short seed. The seed may be truly random. However since the PRNG has a finite state, then it will eventually start repeating the entire sequence again. A computationally limited adversary may not be able to compute the entire sequence for a given seed. However it interests me to consider the case of an all-powerful probabilistic adversary (call that adversary Eve) that is able to compute the all the possible sequences for all the possible seeds (since seeds are finite as well).

Eve has a black-box access to a PRNG, and is able to initialize it with any seed and recover the whole sequence. It doesn't know a priori the length of the sequence but lets arguably assume the existence of a method to deterministically know the sequence length given only the black-box access to the PRNG.

Then consider this following game between Alice and Eve. Alice, a computationally limited Turing machine, also has a black-box access to the same PRNG as Eve, and also has a truly random short seed (S) as input. Alice initializes the PRNG with S and then generates a sequence of bits from the PRNG, of length $\ell$. Alice then chooses any sub-sequence of length $\ell^{\prime}$ and sends it to Eve. Eve should then, using her knowledge of the PRNG, and some random coin tosses, output $S^{\prime}$, her guess of the random input of Alice. There is some probability of getting it right, over the random input of Alice, the coin tosses of Eve, given a certain PRNG and a certain $\ell^{\prime}$. Call that probability $P(S^{\prime} = S)$.

The question is then, given a certain PRNG, what is the least $\ell^{\prime}$ such that $P(S^{\prime} = S)=1$.

I don't know if this has been researched before but I am just recording the question here for me to investigate later. If you have any references if this problem has been tackled before, please share it in the comments :) Thanks.

The class scheduling problem at FCIH and Graph Theory !

The graph scheduling problem in FCIH apparently is not easy to solve. There is many classes, many subjects, student-subject relationship is complicated as it is fine-grained after the credit hours system has been deployed. This result in the schedule being unstable and modified a lot. In this article we seek to model this problem using Graph Theory and see possible solutions, or at least know the exact reason for the problem and the absolute minimum number of resources (time slots, rooms, etc.) needed.

Lets say that our undirected graph consists of vertices representing subjects, and edges representing student-subject relationship. In particular an edge $(i,j)$ is present between subjects $i$ and $j$ is there is a student taking both subjects.

We are going now to assign each vertex a "label" or a "color" representing its time slot (e.g. color$(i)=$ "4th time slot in Monday". We put a restriction that two neighboring vertices (i.e. having an edge between them: a student is taking them both) cannot have the same color; because the student taking both can not attend more than one subject in a time slot. This is the graph vertex coloring problem: given a graph, color its vertices such that no neighboring vertices have the same color. The trivial solution is to give each vertex a unique color. But this is not an interesting solution because you have limited number of color (time slots) and many subject; usually more than the number of time slots.

We might be interested in minimizing the number of colors used. The minimum number of colors needed to color a graph is called the graph's chromatic number, and computing that number is an NP-complete problem, and so there is no efficient algorithm to solve it exactly in the worst case unless P=NP. We may be interested though in a way to approximate it, there is an algorithm to approximate the chromatic number within a multiplicative factor. Notice that knowing the minimum number of colors doesn't mean we found such a coloring.