Non-Uniform Reductions

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