Tightening the Compression Hierarchies
Navid Talebanfard
Abstract:
Fix t, k and n such that k < n <= t and let EASY^n_{t,k} be the set of
all strings of length n that are generated by programs of size k in at
most t steps. It is not hard to see that for sufficiently large t (in
fact for t' > t log t for technical reasons) we have EASY^n_{t,k} ⊆
EASY^n_{t',k'}. But can we get a strict inclusion, or equivalently, is
there an string x that is generated by some k-bit program in t' steps
but cannot be generated in t steps from k-bit programs? If so what is
the smallest t for which a strict inclusion holds? Consider "the first
(in lexicographic order) x \in {0,1}^n that is not generated in t
steps by any program of size k". The statement in quotations is
already a description of that x and it takes 2^k*t*log(t) steps to
output x. This shows that EASY^n_{t,k} ⊂ EASY^n_{2^k*t*log(t), k}.
But is this exponential gap really needed? This question that still
remains open will be the central topic of this thesis. We will examine
different variants of it and will demonstrate its connection with
deterministic simulations of randomized computation.