期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2009
卷号：2009
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：Informally, a language L has speedup if, for any Turing machine for L, there exists one that is better. Blum showed that there are computable languages that have almost-everywhere speedup. These languages were unnatural in that they were constructed for the sole purpose of having such speedup. We identify a condition apparently only slightly stronger than P!=NP which implies that accepting any coNP-complete language has an infinitely-often (i.o.) superpolynomial speedup and NP!=coNP. We also exhibit a natural problem which unconditionally has a weaker type of i.o. speedup based upon whether the full input is read. Neither speedup pertains to the worst case.
