Upward Separation for FewP and Related Classes
Lists
Only you see this
Abstract
This paper studies the range of application of the upward separation technique that has been introduced by Hartmanis to relate certain structural properties of polynomial-time complexity classes to their exponential-time analogs and was first applied to the class NP [12]. Later work revealed the limitations of the technique and identified classes defying upward separation. In particular, it is known that coNP as well as certain promise classes such as BPP, R, and ZPP do not possess upward separation in all relativized worlds [13,15], and it had been suspected 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 that, 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, Longpré, and Spaan's recently discovered tally encoding of sparse sets. As consequences of our main result, we obtain upward separations for various known counting classes such as ⊕P, co, SPP, and LWPP. Some applications and open problems are also discussed.
BibTeX
@inproceedings{rao1994upward,
author = {Rajesh P. N. Rao and Jörg Rothe and Osamu Watanabe},
title = {{Upward Separation for FewP and Related Classes}},
booktitle = {Inf. Process. Lett},
year = {1994},
url = {https://openreview.net/forum?id=eO92J5R2EN},
}Loading related content...