Show simple item record

dc.contributor.authorBuhrman, Harryen_US
dc.contributor.authorHescott, Benjaminen_US
dc.contributor.authorHomer, Stevenen_US
dc.contributor.authorTorenvliet, Leenen_US
dc.date.accessioned2011-10-20T04:49:43Z
dc.date.available2011-10-20T04:49:43Z
dc.date.issued2008-02-15en_US
dc.identifier.urihttp://hdl.handle.net/2144/1700
dc.description.abstractWe 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.en_US
dc.language.isoen_USen_US
dc.publisherBoston University Computer Science Departmenten_US
dc.relation.ispartofseriesBUCS Technical Reports;BUCS-TR-2008-007en_US
dc.subjectComplexity classesen_US
dc.subjectNon-uniform complexityen_US
dc.subjectReductionsen_US
dc.subjectNon-relativizing methodsen_US
dc.titleNon-Uniform Reductionsen_US
dc.typeTechnical Reporten_US


Files in this item

This item appears in the following Collection(s)

Show simple item record