BOUNDING THE COMPLEXITY OF ADVICE FUNCTIONS

Authors
GAVALDA R
Citation
R. Gavalda, BOUNDING THE COMPLEXITY OF ADVICE FUNCTIONS, Journal of computer and system sciences, 50(3), 1995, pp. 468-475
Citations number
27
Categorie Soggetti
System Science","Computer Science Hardware & Architecture","Computer Science Theory & Methods
Journal title
Journal of computer and system sciences → ACNP
ISSN journal
00220000
Volume
50
Issue
3
Year of publication
1995
Pages
468 - 475
Database
ISI
SICI code
0022-0000(1995)50:3<468:BTCOAF>2.0.ZU;2-G
Abstract
It was known that every set A in P/poly has an advice function in PF(S igma(2)(P)(A)). This paper shows that A also has an advice function in PF(NP(A)+Sigma(3)(P)). From this new bound, it is shown that separati ng Delta(2)(P) and Sigma(2)(P) relative to a set in P/poly is as hard as obtaining the same separation, unrelativized. (C) 1995 Academic Pre ss,Inc.