Takes any file. proceed with this algorithm
1.try to compress it with ZIP if it reduces size proceed to step 1. if not step.2. Pick a short random string and XOR the file with it. proceed to step 1 until you reduce file size.
3.record all random strings and result file.
The problem is that the size of the random strings will be at least as big as the amount you reduced from the ZIP file. Making the whole exercise pointless.
Name:
Anonymous2011-06-24 2:41
>>3
what if you only record the seed needed for the PRNG to generate the strings and when decompressing, bruteforce your way through the possible strings the RNG could have generated
although my intuition tells me that the amount of tries needed to reduce the file size grows exponentially as the file size goes down.. but if someone can be arsed to prove that wrong, then try it and tell me the results. i am too lazy
Theorem 1.1: Given a compression algorithm f and positive integer k, there exist finitely many symbol strings compressible by f to less than k bytes. Proof: Pigeonhole principle. QED.
Theorem 1.2: There exists no algorithm which compresses all strings. Proof: Pigeonhole principle. QED.