Genericity and Measure for Exponential Time
Genericity and Measure for Exponential Time
复制标题
指数时间的通用性和度量
DOI：
10.1016/0304-3975(96)89424-2
复制
发表时间：
1994
期刊：
影响因子：
--
通讯作者：
S. Terwijn
中科院分区：
文献类型：
--
作者：
K. Ambos;Hans;S. Terwijn
最近，Lutz[14，15]引入了勒贝格测度的一个多项式时间有界版本。他和其他人(见[11，13-18，20])使用这个概念来研究指数时间(E=DTIME(2lin))的数量结构。此前，Ambos-Spies等人。文[2，3]引入了多项式时间有界的泛性概念，并利用它们研究了NP(在适当的假设下)和E的结构性质。证明了对于任意c-⩾1，NC-一般集类都有p-测度1，这使得我们可以简化和推广某些p-测度1-结果。为了说明一般集的能力，我们以Juedes和Lutz[11]的小跨度定理为例，证明了有界查询约简的一个推广。
Recently, Lutz [14, 15] introduced a polynomial time bounded version of Lebesgue measure. He and others (see e.g. [11, 13–18, 20]) used this concept to investigate the quantitative structure of Exponential Time (E = DTIME (2lin) ). Previously, Ambos-Spies et al. [2, 3] introduced polynomial time bounded genericity concepts and used them for the investigation of structural properties of NP (under appropriate assumptions) and E. Here we relate these concepts to each other. We show that, for any c ⩾ 1, the class of nc-generic sets has p-measure 1. This allows us to simplify and extend certain p-measure 1-results. To illustrate the power of generic sets we take the Small Span Theorem of Juedes and Lutz [11] as an example and prove a generalization for bounded query reductions.