For a class of finite graphs, we define a limit object relative to some computationally restricted class of functions. The properties of the limit object then reflect how a computationally restricted viewer "sees" a generic instance from the class. The construction uses Kraj\'i\v{c}ek's forcing with random variables [7]. We prove sufficient conditions for universal and existential sentences to be valid in the limit, provide several examples, and prove that such a limit object can then be expanded to a model of weak arithmetic. We then take the limit of all finite pointed paths to obtain a model of arithmetic where the problem OntoWeakPigeon is total but Leaf (the complete problem for $\textbf{PPA}$) is not. This can be viewed as a logical separation of the oracle classes of total NP search problems, which in our setting implies standard nonreducibility of Leaf to OntoWeakPigeon.
翻译:对于某类有限图形, 我们定义了一个相对于某些计算限制的功能类别的限制对象。 限制对象的属性会反映一个计算限制的查看器“ 查看” 如何从该类中找到一个通用实例。 构造使用 Kraj\' i\ v{c}ek 的随机变量[ 7] 。 我们证明, 普遍性和存在性判决的条件在限制范围内是有效的, 提供了几个例子, 并证明这样的限制对象随后可以扩展为微弱的算术模型 。 然后, 我们使用所有限制点路径的限度来获取一个计算模型, 其中OntoWeakPigeon的问题是全部的, 但Leaf( $\ textbf{PA}$的完整问题) 并不是。 这可以被视为整个 NP 搜索问题的奥克莱类的逻辑分解, 在我们的设置中, 意味着Leaf 的标准不可降低 OntoWeakPigeon 。