2010-01-19
Unconditional Lower Bounds Against Advice
Publication
Publication
Presented at the
Algebraic Methods in Computational Complexity, 2009 (October 2009), Wadern, Germany
We show several unconditional lower bounds for exponential time classes against polynomial time classes with advice, including: 1. For any constant c, NEXP 6 PNP[nc]/nc 2. For any constant c, MAEXP 6 MA/nc 3. BPEXP 6 BPP/no(1) It was previously unknown even whether NEXP NP/n0.01. For the probabilistic classes, no lower bounds for uniform exponential time against advice were known before. We also consider the question of whether these lower bounds can be made to work on almost all input lengths rather than on infinitely many. We give an oracle relative to which NEXP i.o.NP, which provides evidence that this is not possible with current techniques.
| Additional Metadata | |
|---|---|
| , , , , | |
| doi.org/10.4230/DagSemProc.09421.8 | |
| Dagstuhl Seminar Proceedings | |
| Algebraic Methods in Computational Complexity, 2009 | |
| Organisation | Centrum Wiskunde & Informatica, Amsterdam (CWI), The Netherlands |
|
Buhrman, H., Fortnow, L., & Santhanam, R. (Rahul). (2010). Unconditional Lower Bounds Against Advice. In Dagstuhl Seminar Proceedings. doi:10.4230/DagSemProc.09421.8 |
|
