Computing functions with parallel queries to NP

All of RECERCAT

To access the full text documents, please follow this link: http://hdl.handle.net/2117/96815

dc.contributor.author	Jenner Núñez, Birgit
dc.contributor.author	Torán Romero, Jacobo
dc.date	1993-03
dc.identifier.citation	Jenner, B., Toran, J. "Computing functions with parallel queries to NP". 1993.
dc.identifier.uri	http://hdl.handle.net/2117/96815
dc.language.iso	eng
dc.rights	info:eu-repo/semantics/openAccess
dc.subject	Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
dc.subject	Theta_2^p class of languages
dc.subject	Polynomial time truth-table reduction
dc.subject	Parallel queries to NP
dc.title	Computing functions with parallel queries to NP
dc.type	info:eu-repo/semantics/publishedVersion
dc.type	info:eu-repo/semantics/report
dc.description.abstract	The class "Theta_2^p" of languages polynomial time truth-table reducible to sets in NP has a wide range of different characterizations. We survey some of them studying the classes obtained when the characterizations are used to define functions instead of languages. We show that in this way the three function classes FP_parallel^NP, FP_log^NP and FL_log^NP are obtained. We give an overview about the known relationships between these classes, including some original results.