Non-Uniform Reductions
Harry Buhrman, Benjamin J. Hescott, Steven Thomas Homer, Leen Torenvliet · Theory of Computing Systems · 2009
We study properties of non-uniform reductions and related completeness notions. We strengthen several results of Hitchcock and Pavan (ICALP (1), Lecture Notes in Computer Science, vol. 4051, pp. 465–476, Springer, 2006 ) 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, among other things that non-uniformity can be removed at the cost of more queries. In line with Post’s program for complexity theory (Buhrman and Torenvliet in Bulletin of the EATCS 85, pp. 41–51, 2005 ) we connect such ‘uniformization’ properties to the separation of complexity classes.