How to Compress the Solution

03/09/2023

∙

by   Samuel Epstein, et al.

∙

0

∙

share

Using derandomization, we provide an upper bound on the compression size of solutions to the graph coloring problem. In general, if solutions to a combinatorial problem exist with high probability and the probability is simple, then there exists a simple solution to the problem. Otherwise the problem instance has high mutual information with the halting problem.