8
$\begingroup$

I have $m$ bit vectors, each of which is composed by $m$ bits. Let's denote with $v_i[j]$ the $j$-th bit of the $i$-th vector, $i,j \in [1, m]$. Each bit vector $v_i$ is subject to the following 2 restrictions:

  1. $v_i[j] = 0\ \forall j \geq i$.
  2. $v_i[j] = 1\ \forall j < i - \frac{m}{log(m)}$.
  3. Those bits that do not fall in the restrictions above can be either $0$ or $1$, but in such case the number of $0$'s can be at most $12$.

Now I have another bit vector $s$, of $m$ bits: initially all the $m$ bits of $s$ are set to $1$. By "applying $v_i$ to $s$" I mean performing a bitwise AND between $s$ and $v_i$, and then storing the result in $s$. I'm interested in the evolution of $s$ after repeated applications of the vectors $v_1, ..., v_m$ given in input.

Let's call those "repeated applications" a trajectory, and let's define such trajectory more formally. A trajectory is a sequence composed by at most $m$ vectors (selected from those $v_1, ..., v_m$ given in input) such that if $v_i$ is in the sequence, then all the $v_j$ after it must have $j < i$. So, for example, $<v_8, v_3>$ is a trajectory, while $<v_3, v_8, v_7>$ is not (because $8\geq3$).

Clearly, there are $2^m$ different trajectories. Let $S=\emptyset$. Suppose to take $s = 1^m$ and to let it undergo a trajectory $T_1$: for each step of the trajectory $T_1$, put the new value taken by $s$ in $S$. Then repeat the same process for another trajectory $T_2$ (always starting from $s=1^m$, and always putting every new value of $s$ in $S$). Then again, until you tried all the possible $2^m$ trajectories. At the end, the set $S$ will contain all the possible values that $s$ may ever assume given the vectors in input.

Questions

  1. I have $v_i, ..., v_m$ in input. I want to know $|S|$, i.e. how many distinct values may $s$ ever assume. Of course, I want to compute $|S|$ efficiently, i.e. without trying all the possible trajectories one by one.
  2. Suppose to remove the 2nd restriction on the vectors in input. How doing so affects $|S|$?
  3. More importantly, what I most care about is how $|S|$ grows with $m$. Is $|S|$ at most polynomial in $m$? Is $|S|$ at most sub-exponential in $m$? Or do there exist bad instances on which $|S|$ is necessarily exponential in $m$?

The following figure is an example with $m=17$: Example

I'm collecting experimental data in order to try to figure out which is the relationship between $m$ and $|S|$. So far, experiments seems to suggest that $|S|$ grows faster than $m^3$ and slower than $m^4$. However, for the moment those data have not much significance: I was only able to make tests up to $m = 90$, so there may be a big hidden constant or some other factor that lets an exponential law look like a polynomial law for small $m$. I need help in figuring out the asymptotic behaviour of $|S|$ with respect to $m$.

$\endgroup$
  • 4
    $\begingroup$ @Downvoter: Why downvoting? Please motivate. $\endgroup$ – Giorgio Camerani Sep 26 '11 at 20:08
  • $\begingroup$ Aren't the trajectories overcomplicating it? You could just talk about subsets of $\{1\ldots m\}$ $\endgroup$ – Peter Taylor Sep 27 '11 at 22:18
  • $\begingroup$ @Peter: Yes a trajectory is nothing more than a subset of $\{1, ..., m\}$. I've just thought that talking about trajectories would have given a more intuitive, "visual" picture of the problem. I wanted to put the accent on the evolution of the vector $s$, to stress the fact that I'm interested in how many different values can $s$ assume during all its possible evolutions. $\endgroup$ – Giorgio Camerani Sep 28 '11 at 8:28
  • 3
    $\begingroup$ @Walter: One possible reason for the downvotes is the title of the question, which is of no help. You may want to rephrase it so that it does not contain "help" and maybe hint at the objects you want to count. Cheers! $\endgroup$ – Michaël Cadilhac Sep 29 '11 at 16:12
  • $\begingroup$ @MichaëlCadilhac: Yes, admittedly the title is very generic. Probably I will change it to something more "attractive". Thanks for your hint, cheers! $\endgroup$ – Giorgio Camerani Sep 29 '11 at 17:55
8
+100
$\begingroup$

I've rethought this and my initial bound was correct. In the worst case, $|S| = \Theta(m \; 2^\frac{m}{\lg m})$

Proof is in two parts. Firstly, $|S| = O(m \; 2^\frac{m}{\lg m})$. Consider the possible values of $s$ of a trajectory which ends at $v_x$. Every bit $s[j]$ for $j \ge x$ is 0, and every bit $s[j]$ for $j < x - \frac{m}{\lg m}$ is 1. Therefore there are only $2^\frac{m}{\lg m}$ values which $s$ can take. Multiply up by the number of $v_x$ and we have the upper bound.

Secondly, consider

    0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
    0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
    0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1
    0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1
    0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1 1
    0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1 1
    ...
    0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1
    0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1

I assert that this scheme gives you $|S| = \Omega(m \; 2^\frac{m}{\lg m})$. For each column $v_x$ consider also the $(\frac{m}{\lg m}-2)$ columns to its right. Each of the $2^{\frac{m}{\lg m}-2}$ combinations of them gives a different $s$, and in each of those $s$ the top set bit is the top set bit of $v_x$, so there is no double-counting between different $v_x$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer. Do you have any clue whether the third constraint (i.e. not more than $12$ zeros) makes any difference? In other words, do you believe that restricting the zeros to at most $12$ implies that the number of different values introduced by trajectories ending at $v_x$ is much less than $2^{m/logm}$ (by "much less" I mean not exponential in ${m/logm}$)? My sensation is that it doesn't make any difference: even if we allow at most $1$ zero it seems that we may generate $2^{m/logm}$ different values for at least one $v_x$. $\endgroup$ – Giorgio Camerani Sep 29 '11 at 8:22
  • $\begingroup$ @WalterBishop, my example uses not more than 1 zero. $\endgroup$ – Peter Taylor Sep 29 '11 at 8:26
  • $\begingroup$ Sorry I've parsed both the answer and the example too fast. $\endgroup$ – Giorgio Camerani Sep 29 '11 at 9:01
  • $\begingroup$ @WalterBishop, although if you restrict the number of 1s instead (no more than $k$ of the free values in a vector can be 1) you get $|S| = O(m^{k+1})$ $\endgroup$ – Peter Taylor Sep 30 '11 at 16:16
  • $\begingroup$ How do you derive $|S|=O(m^{k+1})$ in such case? To me, it seems that in such case we would have $|S|=O(m \cdot 2^{k})=O(m)$ (since $k$ is constant). Because AND-ing 2 vectors, a $1$ may become a $0$ but a $0$ can't become a $1$: thus, regardless of the fact that our "sliding window" has $m/logm$ vectors, we may generate at most $2^k$ different vectors for each of the $m$ position of the "sliding window". Am I missing something? $\endgroup$ – Giorgio Camerani Oct 2 '11 at 18:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.