Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
430822 | Journal of Computer and System Sciences | 2006 | 30 Pages |
Abstract
Resolving an issue open since Fenner, Fortnow, and Kurtz raised it in [S. Fenner, L. Fortnow, S. Kurtz, Gap-definable counting classes, J. Comput. System Sci. 48 (1) (1994) 116–148], we prove that LWPP is not uniformly gap-definable and that WPP is not uniformly gap-definable. We do so in the context of a broader investigation, via the polynomial degree bound technique, of the lowness, Turing hardness, and inclusion relationships of counting and other central complexity classes.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics