Automatic Complexity

7 Logical depth and automatic complexity

7.1 Introduction

Logical depth was defined by Chaitin in 1977 [11] and further studied by Bennett in 1986. It is essentially the time it takes to verify a witness of Kolmogorov complexity. We demonstrate that for automatic complexity, logical depth arises as the difficulty of determining the unique solvability of certain knapsack problems.

A word is deep not so much if it has no simple description but rather if its simplest description is hard to understand and verify. For example, the factorization

$\begin{array}{c}2001=3\times 23\times 29\end{array}$

is laborious to find, but relatively simple to verify. In that sense, it is not deep. In this chapter we uncover a quite concrete instance of this idea of logical depth. To do so we replace ...