ECCC-Report TR23-008https://eccc.weizmann.ac.il/report/2023/008Comments and Revisions published for TR23-008en-usSun, 05 Feb 2023 10:30:13 +0200
Paper TR23-008
| Limits of structures and Total NP Search Problems |
Ond?ej Ježil
https://eccc.weizmann.ac.il/report/2023/008For 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í?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.Sun, 05 Feb 2023 10:30:13 +0200https://eccc.weizmann.ac.il/report/2023/008