Non-Uniform Reductions
Date
2008-02-15
DOI
Authors
Buhrman, Harry
Hescott, Benjamin
Homer, Steven
Torenvliet, Leen
Version
OA Version
Citation
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.