Reductions With One Bit Of Advice

Abstract

Given a solution to a specific problem within some resource bound, can this solution help solve a different problem with some small additional cost? This question is fundamental within the study of computational complexity. The conversion of one problem to another is made formal by the notion of a reduction (think subroutine.) Reductions are commonly used to show that a set is hard for a particular complexity class, here a set is hard if every set in the class efficiently reduces to it. It is not known whether different notions of reductions behave the same for certain complexity classes.

In this work, we focus on non-uniform many-one reductions. A many- one reduction is said to be non-uniform if it is given additional advice which depends only on the length of the input. We consider the smallest amount of advice possible, namely one bit. Surprisingly this one bit is powerful. We study these new reductions and the complete sets they generate in the common complexity classes EXP, NEXP and NP.

We show for exponential time that the sets complete under polynomial- time many-one reductions with one bit of advice are different from the sets that are complete under polynomial-time many-one reductions with no advice. We also show that the many-one complete sets with one bit of advice within the delta levels of the polynomial hierarchy are also complete using polynomial-time non-adaptive reductions. We conclude by observing that an open question regarding the behavior of these reductions in EXP is equivalent to separating complexity classes.