39.5 Exercises

Factual

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?

Problem 1

The interpreter must be 55,000 bits or less. If it is, we can simply decompress the bitstream by running the Python program in the interpreter, using less than 100000 bits total (program + interpreter).

Problem 2

• The problem is a yes-no problem.

• A solution to the problem is efficiently verifiable.

Procedural

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

Problem 1

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}}$.