New answers tagged information-theory
1
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 ...
1
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 ...
1
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 ...
2
0
100
101
110
11100
11101
11110
11111
2
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, ...
Top 50 recent answers are included
