Limits of structures and Total NP Search Problems
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909370985480192 |
|---|---|
| author | Ježil, Ondřej |
| author_facet | Ježil, Ondřej |
| contents | For an infinite class of finite graphs of unbounded size, we define a limit object, to be called a $\textit{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, Forcing with random variables and proof complexity 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 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 \text{PV}_1(f)$ where the problem $\textbf{RetractionWeakPigeon}$ is total but $\textbf{WeakPigeon}$, the complete problem for $\textbf{PWPP}$, is not. Thus, we obtain a new proof of this unprovability and show it implies that $\textbf{WeakPigeon}$ is not many-one reducible to $\textbf{RetractionWeakPigeon}$ in the oracle setting. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2301_13603 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Limits of structures and Total NP Search Problems Ježil, Ondřej Logic Computational Complexity For an infinite class of finite graphs of unbounded size, we define a limit object, to be called a $\textit{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, Forcing with random variables and proof complexity 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 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 \text{PV}_1(f)$ where the problem $\textbf{RetractionWeakPigeon}$ is total but $\textbf{WeakPigeon}$, the complete problem for $\textbf{PWPP}$, is not. Thus, we obtain a new proof of this unprovability and show it implies that $\textbf{WeakPigeon}$ is not many-one reducible to $\textbf{RetractionWeakPigeon}$ in the oracle setting. |
| title | Limits of structures and Total NP Search Problems |
| topic | Logic Computational Complexity |
| url | https://arxiv.org/abs/2301.13603 |