Refining logical characterizations of advice complexity classes

Consultar RECERCAT

Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/83486

dc.contributor	Universitat Politècnica de Catalunya. Departament de Ciències de la Computació
dc.contributor.author	Atserias, Albert
dc.contributor.author	Balcázar Navarro, José Luis
dc.date	1997-05
dc.identifier.citation	Atserias, A., Balcazar, J. L. "Refining logical characterizations of advice complexity classes". 1997.
dc.identifier.uri	http://hdl.handle.net/2117/83486
dc.language.iso	eng
dc.relation	LSI-97-40-R
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
dc.subject	Nonuniform complexity classes
dc.subject	Computational complexity
dc.title	Refining logical characterizations of advice complexity classes
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.abstract	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.

Atserias, Albert; Balcázar Navarro, José Luis; Piceno Cabrera, Marie Ely

Atserias, Albert; Balcázar Navarro, José Luis

Atserias, Albert; Müller, Moritz; Oliva Valls, Sergi

Atserias, Albert; Kreutzer, Stephan; Noy Serrano, Marcos

Atserias, Albert; Bonacina, Ilario; Rezende, Susanna F. de; Lauria, Massimo; Nordström, Jakob; Razborov, Alexander

Coordinación

Patrocinio