Characterizations of logarithmic advice complexity classes

The complexity classes P/log and Full-P/log, corresponding to the two standard forms of logarithmic advice for polynomial time, are studied. Characterizations are found in terms of Kolmogorov-simple circuits, bounded query classes, prefix-closed advice, reduction classes of regular or Kolmogorov-regular tally sets, and reduction classes of logarithmically sparse-capturable sets. The proofs are based on the Shannon-Lupanov effect and on the novel technique of “doubly exponential skip”. The techniques can be also applied to polynomial time classes with sublinear advice and to classes based on different uniform counterparts, such as NP, PSPACE, and many others.Postprint (author's final draft