C
C
CS61B Textbook
Search
⌃K
Comment on page

39.5 Exercises

Factual

  1. 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. 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. 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
210000002^{1000000}
 bit sequences of length 1 million, but only
20+21+...2899999+2900000=2(2900000)−1≈29000012^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
290000121000000=1299999\frac{2^{900001}}{2^{1000000}} = \frac{1}{2^{99999}}
.
Previous
39.4 P = NP
Last modified 7mo ago