# Tag Info

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