Paper detail

Kolmogorov-Loveland Sets and Advice Complexity Classes

Loveland complexity is a variant of Kolmogorov complexity, where it is asked to output separately the bits of the desired string, instead of the string itself. Similarly to the resource-bounded Kolmogorov sets we define Loveland sets. We highlight a structural connection between resource-bounded Loveland sets and some advice complexity classes. This structural connection enables us to map to advice complexity classes some properties of Kolmogorov sets first noticed by Hartmanis and thoroughly investigated in Longpré's thesis: 1. Non-inclusion properties of Loveland sets result in hierarchy properties on the corresponding advice complexity classes; 2. Immunity properties of Loveland sets result in the non-existence of natural proofs between the corresponding advice complexity classes, in the sense of Razborov & Rudich.