Non-Uniform Reductions

OpenBU

Show simple item record

dc.contributor.author Buhrman, Harry en_US
dc.contributor.author Hescott, Benjamin en_US
dc.contributor.author Homer, Steven en_US
dc.contributor.author Torenvliet, Leen en_US
dc.date.accessioned 2011-10-20T04:49:43Z
dc.date.available 2011-10-20T04:49:43Z
dc.date.issued 2008-02-15 en_US
dc.identifier.uri http://hdl.handle.net/2144/1700
dc.description.abstract 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. en_US
dc.language.iso en_US en_US
dc.publisher Boston University Computer Science Department en_US
dc.relation.ispartofseries BUCS Technical Reports;BUCS-TR-2008-007 en_US
dc.subject Complexity classes en_US
dc.subject Non-uniform complexity en_US
dc.subject Reductions en_US
dc.subject Non-relativizing methods en_US
dc.title Non-Uniform Reductions en_US
dc.type Technical Report en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search OpenBU


Advanced Search

Browse

Deposit Materials