Skip to main content
3 votes
Accepted

Information content of a real number

In some sense I agree that $\mathcal{U}_{[0,1]}$ has "infinite information" but we should be a little more careful formalizing it. As indeed, Shannon entropy is only defined for discrete ...
Benjamin Kuykendall's user avatar
2 votes
Accepted

What algorithm constructs the optimal code $f$ of size $a$?

Arithmetic codes can get arbitrarily close to the Shannon limit, assuming your model of probabilities is correct. It it typically shown in the context of a binary alphabet, but there's nothing ...
orlp's user avatar
  • 13.6k
1 vote

Information content of a real number

Yes. Its information content (entropy) is infinite.
D.W.'s user avatar
  • 162k
1 vote

Kolmogorov complexity of tuples

Yes, it looks like the two claim are contradictory. I'm pretty sure the Sipser exercise is correct, though it's not trivial to verify. There is a useful hint here, but even given the hint it took me a ...
Benjamin Kuykendall's user avatar
1 vote

NP-HARD optimization problem and instance correlation

I assume in this answer that $A$ is NP-complete, since otherwise it is possible that $A$ is unsolvable, or that the output size is super polynomial in $n$. Assuming $A$ is NP-complete, let $x$ be some ...
Narek Bojikian's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible