Details

Autor(en) / Beteiligte

• Buhrman, Harry
• Chang, Richard
• Fortnow, Lance

Titel

One Bit of Advice

Ist Teil von

• Lecture notes in computer science, 2003, p.547-558

Ort / Verlag

Berlin, Heidelberg: Springer Berlin Heidelberg

Erscheinungsjahr

2003

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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 BH ∶DP⇒ coNP ∶ NP/poly. The stronger assumption that PH ∶ 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 ∶ BH2k ⇔ coNP ∶ NP/k where BH2k denotes the 2k-th level of BH and NP/k denotes the class NP with k-bit advice functions.