Compression, Complexity, and P=NP?
Model 1 vs. Model 2 for Compression
A Flaw in Compression Model 1: Source code for decompression algorithm itself might be highly complex.
Question 1: Comprehensible Compression
Is there a "comprehensible" compression takes as input a target bitstream B, and outputs useful, readable Java code?
Question 2: Optimal Compression
Is there an optimal compression takes as input a target bitstream B, and outputs the shortest possible Java program that outputs this bitstream?
Kolmogorov Complexity
The Java-Kolmogorov complexity K_J (B) is the length of the shortest Java program (in bytes) that generates B.
Fact #1: Kolmogorov Complexity is effectively independent of language. For any bit stream, the Java-Kolmogorov Complexity is no more than a constant factor larger than the Python-Kolmogorov Complexity.
Could write a Python interpreter in Java and then runs the Python program.
It means that most bitstreams are fundamentally incompressible no matter what programming language is used for the compression algorithm.
Space/Time Bounded Compression
An optimal compression algorithm takes as input a target bitstream B, and outputs the shortest possible Java program that outputs this bitstream.
No “optimal compression” algorithm exists.
Space Bounded Compression
Takes two inputs, a target bitstream B and a size S, and outputs a Java program of length ≤ S that outputs B.
Does not exist, since it could be used to find K_J (B) by binary searching on S.
Space/Time Bounded Compression
Takes three inputs, a target bitstream B, a size S, a maximum number of lines of bytecode executed T, and outputs a Java program of length ≤ S that outputs B in fewer than T executed lines of bytecode.
For each possible program p of length S or less:
If p compiles, run program p until either:
p terminates.
We output B.
T lines of bytecode are executed.
Runtime:
O(T x 2 ^ S).
Efficient Space/Time Bounded Compression
Need to make a more precise definition of what we mean by “efficient”.
Closely related to an important puzzle in computer science: Does P = NP?
P = NP?
An efficient solution to these three problems (3SAT, Independent Set, and Longest Path) would also give an efficient space/time bounded compression algorithm.
Space/time bounded compression reduces to 3SAT, Independent Set, and Longest Path.
Definition
Two important classes of yes/no problems: P: Efficiently solvable problems. NP: Problems with solutions that are efficiently verifiable.
Examples of problems in P:
Is this array sorted?
Does this array have duplicates?
Examples of problems in NP:
Is there a solution to this 3SAT problem?
In graph G, does there exist a path from s to t of weight > k?
Any decision problem for which a yes answer can be efficiently verified can be transformed into a 3SAT problem. This transformation is also "efficient" (polynomial time).
Last updated