<link rel="stylesheet" href="styles.f3b1fba60ec7970c.css">
Archive Browse journal articles

Publication:
Limits of structures and total NP search problems

Files

Loading...
Thumbnail Image
Primary
Name

CAM.257-Jezil-2026.pdf

Size

792.92 KB

Format

Adobe PDF

Checksum

(MD5):bf647190af0e96a0903f4a580d5c1da6

Date

2026

Translators

Journal Title

ZML: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik

Journal ISSN

Volume Title

ZML: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik - Volume 72

Publisher

ZML: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik

Cite this article

Preferred citation

Ondřej Ježil. "Limits of structures and total NP search problems." Zeitschrift für Mathematische Logik und Grundlagen der Mathematik, Vol. 72 (2026), pp. 135–156. DOI: 10.60866/CAM.257

Research Projects

Organizational Units

Journal

Journal Volume

Item type:Journal Volume,
ZML: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik - Volume 72
ZML: Zeitschrift für Mathematische Logik und Grundlagen der Mathematik (72)

Journal Issue

Associated reviews

Associated publications

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.

Description

Keywords

Endorsement

Review

Supplemented By

Referenced By

Rights and licensing

Except where otherwise noted, this item's license is described as Attribution 4.0 International