Definition and existence of super complexity cores

Abstract

In this paper we define and study super complexity cores of languages L with respect to classes C with L ∉ C. A super complexity core S of L can be considered as an infinite set of strings for which the decision problem for L is very hard to solve with respect to the available “resources” fixed by C even for algorithms which have to compute the correct result only for all inputs x ε S. For example let C = P and S be a super complexity core of L. Then S is infinite and all deterministic Turing machines M, which output 1 on input x ε S ∩ L and O on input x ε S ∩ Pit¯tL, need more than polynomially many steps on all but finitely many inputs x ε S. We prove that for all non-empty, countable classes of languages C which are closed under finite variation, finite union, and under complement and for all languages L ∉ C it follows that such a super complexity core of L with respect to C exists. Moreover we show: Given a recursively enumerable class C of languages and a recursive language L, if there is a super complexity core of L with respect to C, then there exists a recursive super complexity core, too.

Thus for L ∉ BPP (PP, PSPACE,...) there exists a set S such that all BPP Turing machines (PP Turing machines, PSPACE Turing machines,...), which compute the characteristic function of L correctly at least on inputs x ε S, need more than polynomially many steps (tape cells) on almost all inputs x ε S.

Preparation of this paper was supported in part by a fellowship of the Graduiertenkolleg Informatik (Deutsche Forschungsgemeinschaft).