文章基本信息

标题：Unconditional Lower Bounds against Advice
本地全文：下载
作者：Harry Buhrman ; Lance Fortnow ; Rahul Santhanam 等
期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We show several unconditional lower bounds for exponential time classes against polynomial time classes with advice, including: \begin{enumerate} \item For any constant c , \NEXP \P \NP [ n c ] n c \item For any constant c , \MAEXP \MA n c \item \BPEXP \BPP n o (1) \end{enumerate} It was previously unknown even whether \NEXP \NP n 0 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 \io \NP , which provides evidence that this is not possible with current techniques.
关键词：advice , derandomization , diagonalization , lower bounds , Semantic Classes