Algebra view point on computation ??

Today I was trying to make a theoretical model for my peer to peer network simulator. Basically its a network of peers which is modified each loop according to certain rules (either random peer sampling or according to similarity-based clustering). The network is modeled as an adjacency matrix and to modify this matrix I may multiply it by a certain matrix; since the network is closed then it is possible to utilize a permutation matrix for that (peers exchange neighbors with each others). I also use a randomization matrix between each two operations to account for randomness in choice. So if we denote the network (adjacency matrix of the network graph) at cycle $n$ as $G(n)$, then the operation that happens in each cycle of the simulation is $$G(n+1) \leftarrow E \times R \times G(n) .$$ Where $R$ is the random permutation matrix and $E$ is the exchange matrix.

Okay, here comes an observation. Matrix multiplication is not commutative, and hence it allows us to express a sequence of operations (operators) and to express an adaptive computation. So it was fair enough to ask my self a question, non-commutativity actually added more power in this case, unlike the view common in algebras where it gets less interesting as you lose properties. So I though, what if I use Cayley-Dickson construction to make a higher algebra that is not even associative ? What would we get ? Well, I am not if this will be clear to you but I can clearly see that this allows us easily to express a tree, not just a sequence, of operations. The nature of operations might be different than a permutation or rotation, I am not sure of that, but the open question now is since a tree resembles recursion (in some sense), then could this allow us to construct a sort of universal recursive function (which would be turing-complete) ? Even more interestingly, can we construct a certain algebra in such a way to express all and only all such computations that can recognize a certain language, i.e. given a class of languages or a turing machine that recognizes them, can we construct an algebra equivalent to this machine ?

Why would this be interesting ? well, one reason that might occur to me is that if we were able to explicitly construct an algebra for $P$ and another for $NP$ then we might have another way to attack the famous $P=NP$ problem, which would then be equivalent to whether the two algebras are equivalent. This might be an interesting research direction for me, and in fact, I wrote this article as a sort of a TODO to remind me of this idea later when I finish my PhD and be able to pursue a research direction of my own. Thanks for reading and any comments or references are welcome!

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.

Does the universe split each time a qubit is measured ?

In the Many Worlds Interpretation of quantum mechanics it is thought that when a quantum wave function collapses to give one of the possible quantum outcomes, the universe splits into several universes. In each of those universes a different possible outcome is realized. For instance, assuming that a qubit is measured, its wave function collapses to give either up or down (1 or 0). In the Many Worlds Interpretation, the universe is split into two universes where in the first universe they observe 1 and in the second they observe 0. Check the wikipedia photo:



But, apart from that interpretation, each observation has a certain probability defined by Born's rule. That is, if we repeated the measurement (after re-initializing the quantum system to the same state) a very big number of times, then the fraction of times we observe a certain outcome is roughly equal to its probability.

So, if universe is split each time a qubit is measured into two universes, one where 1 is measured and another where 0 is measured, then how do we interpret probability of measurment ? It might be plausible to assume that the probability should hold relatively to each universe. For instance, for each of this universes, it should observe a probability consistent with the probability given by Born's rule. But since all paths are followed (correct me if I am wrong), then there exists exactly one universe (path) of all these branches (in the multiverse tree) where the measurement always took the same value. This was the obvious case for counter-example. It could also be noted that there would be a lot more universes where the probability isn't necessarily consistent the one given by Born's rule (the exact number -in the case of having two possible outcomes, could be given by $n! - \binom{n}{np}$ where $n$ is the number of measurements and $p$ is the probability of measuring one of the outcomes).

Another thing, if we assume that we could have an countably infinite number of measurements, then according the Many Worlds Interpretation, we will end up with an uncountable infinite number of universes.