It is easy to show that Hitting Set is in NP. A solution just needs to
exhibit the set H – one can easily verify in polynomial time whether H is of size k and
intersects each of the sets B1, . . . , Bm.
We reduce from vertex cover. Consider an instance of the vertex cover problem –
graph G = (V, E) and a positive integer k. We map it to an instance of the ...
When $X$ is distributed uniformly over a domain of size $n$, then Shannon entropy, collision entropy and min-entropy are all equal to $\log n$. In a sense, all of these parameters measure the amount of uncertainty in $X$.
In contrast, your proposed definition is always between $0$ and $1$, tending to zero as $X$ gets more unpredictable. This is quite ...
It seems you are interested in how to represent instructions in the most compact size. But that is quite a secondary consideration.
The most important two considerations are: 1. Being able to decode an instruction in the shortest possible time. 2. Determine the length of an instruction in the shortest possible time.
Why is this so important? Let's say ...
This answer assumes that $Y = X + Z \bmod 2I$, which seems more reasonable than the current $Y = X + Z \bmod I$, which would mean that $X$ is effectively chosen from an alphabet of size $I$ rather than $2I$.
The capacity is $\log I$.
For the upper bound,
I(X;Y) = H(Y) - H(Y|X) = H(Y) - H(Z) = H(Y) - 1 \leq \log(2I) - 1 = \log I.
For the lower bound, ...