Título:
|
Simplicity, relativizations, and nondeterminism
|
Autor/a:
|
Balcázar Navarro, José Luis
|
Otros autores:
|
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Facultat d'Informàtica de Barcelona; Universitat Politècnica de Catalunya. LARCA - Laboratori d'Algorísmia Relacional, Complexitat i Aprenentatge |
Abstract:
|
Relativizations of complexity classes in which simple sets exist are considered. A recursive oracle is constructed relative to which a simple set exists for NP. Some other general theorems are proven, showing that the time bounds are not a crucial hypothesis; bounds on the way in which the oracle is accessible, namely the number of queries and/or the number of nondeterministic steps, are shown to be the fundamental hypothesis. As a result, simple sets are shown to exist in many different relativized complexity classes |
Abstract:
|
Peer Reviewed |
Materia(s):
|
-Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat -Complexity, Computational -Simplicity -Relativizations -Nondeterminism -Complexity classes -Simple sets -Recursive oracle -NP -Complexitat computacional |
Derechos:
|
|
Tipo de documento:
|
Artículo - Versión publicada Artículo |
Compartir:
|
|