A Brief on Short Descriptions
Jason Teutsch, Marius Zimand · ACM SIGACT News · 2016
We discuss research developments on the complexity of shortest programs since the turn of the millennium. In particular, we will delve into the phenomenon of list approximation: while it's impossible to compute the shortest description for a given string, we can efficiently generate a short list of candidates which includes a (nearly) shortest description.