Comment on page

# 39.5 Exercises

- 1.True/false: suppose we have a 45000-bit program in Python that outputs a bitstream B. What is the maximum size of an interpreter written in Java that proves the Java-Kolmogorov complexity is less than 100,000?
- 2.What are the two defining properties of an NP problem?

- 1.What is the probability that some sequence of 1 million bits could be compressed to 900,000 bits or less?

There are

$2^{1000000}$

bit sequences of length 1 million, but only $2^0 + 2^1 + ... 2^{899999} + 2^{900000} = 2(2^{900000}) - 1 \approx 2^{900001}$

bit sequences of length 900,000 or less. This means that the probability of any bitsequence being compressed to 900,000 bits or less is $\frac{2^{900001}}{2^{1000000}} = \frac{1}{2^{99999}}$

.Last modified 7mo ago