Non-Uniform Reductions


Show simple item record Buhrman, Harry en_US Hescott, Benjamin en_US Homer, Steven en_US Torenvliet, Leen en_US 2011-10-20T04:49:43Z 2011-10-20T04:49:43Z 2008-02-15 en_US
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


Deposit Materials