####
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:
conference submission.
- Status: conference version under preparation.
- On-line:
- Article on SpringerLink:
link.
- Conference submission available as a PDF file
(with embedded Type 1 fonts): np1.pdf.

#### 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 D^{p}, the second level of the Boolean Hierarchy
(BH). Previous work showed that if BH collapses to D^{p} then coNP
is contained in NP/poly. The stronger assumption that PH collapses to
D^{p} 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 2^{k}-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