Title: Non-Uniform Reductions

Authors: Harry Buhrman, Ben Hescott Steve Homer and Lane Torrenvliet

Date: Feb. 15, 2008

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.