论文标题
pspace函数及其对话的奇异定理
Ergodic Theorems for PSPACE functions and their converses
论文作者
论文摘要
我们在基于资源的设置中启动对有效的千古定理的研究。从经典上讲，可集成函数的Ergodic平均值的收敛性可以任意缓慢。相比之下，我们表明，对于一类PSPACE L1函数，以及一类可计算的PSPACE可计算量化的ergodic转换，所有PSPACE随机物的ergodic平均值都存在，并且等于每个EXP随机的空间平均值。我们建立了一种部分交谈，即PSPACE非随机性可以被描述为Ergodic平均值的非共进性。此外，我们证明有一类资源结合的随机物，即。次级空间随机物，相应的厄贡定理具有精确的相反 - 当且仅当相应的有效ergodic定理对x中时，点x是subexpace随机的。
We initiate the study of effective pointwise ergodic theorems in resource-bounded settings. Classically, the convergence of the ergodic averages for integrable functions can be arbitrarily slow. In contrast, we show that for a class of PSPACE L1 functions, and a class of PSPACE computable measure-preserving ergodic transformations, the ergodic average exists for all PSPACE randoms and is equal to the space average on every EXP random. We establish a partial converse that PSPACE non-randomness can be characterized as non-convergence of ergodic averages. Further, we prove that there is a class of resource-bounded randoms, viz. SUBEXP-space randoms, on which the corresponding ergodic theorem has an exact converse - a point x is SUBEXP-space random if and only if the corresponding effective ergodic theorem holds for x.
