One Bit of Advice


Abstract:

The results in this paper show that coNP is contained in NP with 1 bit of advice (denoted NP/1) if and only if the Polynomial Hierarchy (PH) collapses to Dp, the second level of the Boolean Hierarchy (BH). Previous work showed that if BH collapses to Dp then coNP is contained in NP/poly. The stronger assumption that PH collapses to Dp in the new result allows the length of the advice function to be reduced to a single bit and also makes the converse true. The one-bit case can be generalized to any constant k:
PH collapses to the 2k-th level of BH if and only if coNP is contained in NP/k.
Here, NP/k denotes the class NP with k-bit advice functions.
Last Modified: 29 Oct 2007 20:10:50 EDT by Richard Chang