Limits of structures and total NP search problems

Abstract

For an infinite class of finite graphs of unbounded size, we define a limit object, to be called a wide limit, relative to some computationally restricted class of functions. The limit object is a first-order Boolean-valued structure. The first-order properties of the wide limit then reflect how a computationally restricted viewer sees a generic member of the class. The construction uses arithmetic forcing with random variables (Krajíček, 2011). We give 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. To illustrate the concept, we give an example in which the wide limit relates to total $\mathsf{NP}$ search problems. In particular, we take the wide limit of all maps from ${0,\dots,k-1}$ to ${0,\dots,\lfloor k/2\rfloor-1}$ to obtain a model of $\forall \mathrm{PV}_1(f)$ where the problem $\mathrm{RetractionWeakPigeon}$ is total, but $\mathrm{WeakPigeon}$, the complete problem for $\mathsf{PWPP}$, is not. Thus, we obtain a new proof of this unprovability and show it implies that $\mathrm{WeakPigeon}$ is not many-one reducible to $\mathrm{RetractionWeakPigeon}$ in the oracle setting.