Non-Uniform Reductions
Data(s) |
20/10/2011
20/10/2011
15/02/2008
|
---|---|
Resumo |
We study properties of non-uniform reductions and related completeness notions. We strengthen several results of Hitchcock and Pavan and give a trade-off between the amount of advice needed for a reduction and its honesty on NEXP. We construct an oracle relative to which this trade-off is optimal. We show, in a more systematic study of non-uniform reductions, that among other things non-uniformity can be removed at the cost of more queries. In line with Post's program for complexity theory we connect such 'uniformization' properties to the separation of complexity classes. |
Identificador | |
Idioma(s) |
en_US |
Publicador |
Boston University Computer Science Department |
Relação |
BUCS Technical Reports;BUCS-TR-2008-007 |
Palavras-Chave | #Complexity classes #Non-uniform complexity #Reductions #Non-relativizing methods |
Tipo |
Technical Report |