7 ms·

I thought of a potential loophole. What about a non-deterministic extractor? Let's say you can make your program smaller by having only a 1% chance of extract

I thought of a potential loophole. What about a non-deterministic extractor? Let's say you can make your program smaller by having only a 1% chance of extracting perfectly. Just submit the program (for an expected) 100 times and claim your prize.

svantana 7y ago
Through the magic of information theory, I can tell you that this particular trick will save you log2(100) = 6.6 bits. Probably not enough to make a difference.
- MilesTeg 7y ago
  I see. You are right.