One Bit of Advice
- Authors: H. Buhrman, R. Chang and L. Fortnow
- Cite as:
in Proceedings of the 20th Annual Symposium on Theoretical Aspects
of Computer Science, Springer-Verlag Lecture Notes in Computer
Science #2607, 547-558, February-March 2003.
- Previous incarnations:
- NEC Research Institute Technical Note #2002-017N.
- Most readable version:
- Status: conference version under preparation.
- Article on SpringerLink:
- Conference submission available as a PDF file
(with embedded Type 1 fonts): np1.pdf.
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.
29 Oct 2007 20:10:50 EDT