Refining logical characterizations of advice complexity classes
Albert Atserias, José Luis Balcázar Navarro · LA Referencia (Red Federada de Repositorios Institucionales de Publicaciones Científicas) · 1997
: Numerical relations in logics are known to characterize, via the finite models of their sentences, polynomial advice nonuniform complexity classes. These are known to coincide with reduction classes of tally sets. Our contributions here are: 1/ a refinement of that characterization that individualizes the reduction class of each tally set, and 2/ characterizing logarithmic advice classes via numerical constants, both in the (rather easy) case of C/log and in the more complex case of Full-C/log; this proof requires to extend to classes below P the technical characterizations known for the class Full-P/log. 1. Introduction Many complexity classes are captured by appropriate logics. Here we focus on nonuniform complexity classes. They have many characterizations in various, sometimes surprising terms, and thus become of interest in several approaches to computational complexity. See [BDG95] and the references there. (They are defined in the preliminaries below.) In particular, [M90] pr...