THE STRUCTURE OF LOGARITHMIC ADVICE COMPLEXITY CLASSES

A nonuniform class called here Full-P/log, due to Ko, is studied. It c orresponds to polynomial time with logarithmically long advice. Its im portance lies in the structural properties it enjoys, more interesting than those of the alternative class P/log; specifically its introduct ion was motivated by the need of a logarithmic advice class closed und er polynomial-time deterministic reductions. Several characterizations of Full-P/log are shown, formulated in terms of various seas of tally sets with very small information content. A study of its inner struct ure is presented, by considering the most usual reducibilities and loo king for the relationships among the corresponding reduction and equiv alence classes defined from these special tally sets. (C) 1998-Elsevie r Science B.V. All rights reserved.