LWPP and WPP are not uniformly gap-definable
作者：
Highlights：
•
摘要
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.
论文关键词：Complexity classes,Gap-definability,Turing hardness,Polynomial degree bounds,Relativization theory
论文评审过程：Received 21 May 2004, Revised 23 November 2005, Available online 21 February 2006.
论文官网地址：https://doi.org/10.1016/j.jcss.2006.01.002
