UPWARD SEPARATION FOR FEWP AND RELATED CLASSES

This paper studies the range of application of the upward separation t echnique that has been introduced by Hartmanis to relate certain struc tural properties of polynomial-time complexity classes to their expone ntial-time analogs and was first applied to the class NP [12]. Later w ork revealed the limitations of the technique and identified classes d efying upward separation. In particular, it is known that coNP as well as certain promise classes such as BPP, R, and ZPP do not possess upw ard separation in all relativized worlds [13,15], and it had been susp ected that this was also the case for other promise classes such as UP and FewP [1]. In this paper, we refute this conjecture by proving tha t, in particular, FewP does display upward separation, thus providing the first upward separation result for a promise class. In fact, this follows from a more general result the proof of which draws heavily on Buhrman, Longpre, and Spaan's recently discovered tally encoding of s parse sets. As consequences of our main result, we obtain upward separ ations for various known counting classes such as +P, coC=P, SPP, and LWPP. Some applications and open problems are also discussed.