One Bit of Advice Export

@misc{citeulike:101532, 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 , the second level of the Boolean Hierarchy (BH). Previous work showed that BH  D =) coNP  NP=poly. The stronger assumption that PH  D 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  BH 2 k ...}, author = {Richard, Harry B.}, citeulike-article-id = {101532}, citeulike-linkout-0 = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.6417}, keywords = {disease, epidemiology, responsibility}, posted-at = {2008-02-26 15:50:44}, priority = {4}, title = {One Bit of Advice}, url = {http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.6417} }

TY - GEN ID - citeulike:101532 L3 - citeulike-article-id:101532 N2 - 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 , the second level of the Boolean Hierarchy (BH). Previous work showed that BH  D =) coNP  NP=poly. The stronger assumption that PH  D 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  BH 2 k ... TI - One Bit of Advice KW - disease KW - epidemiology KW - responsibility AU - Richard, Harry UR - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.2.6417 ER -