# Limits of structures and Total NP Search Problems111This work has been
supported by Charles University Research Center program No.UNCE/SCI/022 and by
the GA UK project No. 246223.

Ondřej Ježil
<EMAIL_ADDRESS>
(Faculty of Mathematics and Physics, Charles University222Sokolovská 83,
Prague, 186 75, The Czech Republic)

###### Abstract

For an infinite class of finite graphs of unbounded size, we define a limit
object, to be called _wide limit_ , relative to some computationally
restricted class of functions. The properties of the wide limit then reflect
how a computationally restricted viewer “sees” a generic instance from the
class. The construction uses arithmetic forcing with random variables [10]. 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
wide limit of all finite pointed paths to obtain a model of arithmetic where
the problem OntoWeakPigeon is total but Leaf (the complete problem for PPA) is
not. This logical separation of the oracle classes of total NP search problems
in our setting implies that Leaf is not reducible to OntoWeakPigeon even if
some errors are allowed in the reductions.

##  1 Introduction

There exist several logical constructions of limits of classes of finite
structures such as the ultraproduct and the compactness theorem. The latter
was used in [3] to prove the $0$–$1$ law for structures over relational
vocabularies.

In combinatorics there are also several notions of limits of finite graphs.
For example the dense graph limit defined for a sequence of graphs
${\\{G_{k}\\}}_{k>0}$ satisfying the condition that

$t(F,G_{n})=\frac{\lvert\hom(F,G)\rvert}{\lvert G_{n}\rvert^{\lvert
F\rvert}},$

converges for every fixed connected graph $F$, where $\hom(F,G)$ denotes the
set of all graph homomorphisms from $F$ to $G$. This provided a framework (see
[11]) to restate and find new proofs for results in extremal graph theory —
for instance Goodman’s theorem relating the number of edges to the number of
triangles in a graph. There are other notions of limits of sequences of
graphs, and we refer the interested reader to [14]. Another recent use of
limit objects for the results of extremal combinatorics was by Razborov in
[15].

In this work, we define a new construction of a limit object. Given a class of
finite graphs $\mathcal{G}$, whose vertex sets are initial segments of
$\mathbb{N}$, we can stratify it into the sequence of sets
$\\{\mathcal{G}_{k}\\}_{k=1}^{\infty}$ as follows

$\mathcal{G}_{k}=\\{\omega\in\mathcal{G};\omega\text{ has $\\{0,\dots,k-1\\}$
as its vertex set}\\}.$

Our construction would yield a pseudofinite structure if
$\lim_{k\to\infty}\lvert\mathcal{G}_{k}\rvert=1$, but an ordinary application
of the compactness theorem suffices for that, we therefore generally care
about the case, where
$\lim_{k\to\infty}\lvert\mathcal{G}_{k}\rvert=\infty$.333The case where the
limit tends to some other positive number results in a structure which after
collapsing to a two-valued boolean algebra becomes pseudofinite too. We call
such a sequence of sets of graphs a _wide sequence_ and the limit object its
_wide limit_.

We will give a full definition in Section 3, but we describe some important
properties here. For a class $F$ of functions (typically chosen to be a class
with some computational restrictions) we define the wide limit denoted
$\lim_{F}\mathcal{G}_{n}$, where $n$ is a technical parameter to be defined
later. The wide limit $\lim_{F}\mathcal{G}_{n}$ is a Boolean-valued
graph444Generally, we can do this with any $L$-structures for some first order
language $L$. The limit object is then a Boolean-valued $L$-structure
$\lim_{F}\mathcal{G}_{n}$. In this work we restrict ourselves to the language
of graphs $L=\\{E\\}$ to simplify the presentation. — its edge relation does
not only permit the truth values 0 and 1 but also many other values from some
infinite complete Boolean algebra $\mathcal{B}$. This algebra is in fact also
a $\sigma$-algebra with a measure $\mu$ on it, so to any statement formulated
as a first order sentence $\varphi$ we can assign a real number
$\mu({[\\![}\varphi{]\\!]})\in[0,1]$ which measures how far is the truth value
of $\varphi$ (denoted ${[\\![}\varphi{]\\!]}$) from the value 0. The key
method we use is arithmetical forcing with random variables, developed in
[10], which allows us to construct models of (weak) arithmetical theories and
by restricting to a language of graphs gives us Boolean-valued graphs. In
these Boolean-valued graphs, validity of existential quantifiers corresponds
to the ability of $F$ to solve search problems over the class of graphs we are
considering. If an existential sentence $(\exists x)\varphi(x)$ is not valid
in the limit but is valid in the structures in $\mathcal{G}_{k}$ we can
conclude that functions from $F$ cannot solve the total search problem given
by $\varphi(x)$.

Our limit object can be expanded to the original model that Krajíček’s method
would otherwise construct. We prove (Theorem 5.8) that the truth values of
first order sentences concerning the object are preserved even when evaluated
in the model of arithmetic relativized to the wide limit (under a mild
condition on the family $F$).

As an application of this construction, we take the limit of all finite paths
starting at the vertex $0$, relative to the class of functions computed by
oracle trees of subexponential depth, and obtain the Boolean-valued graph
$\lim_{F_{\text{nb}}}*\text{PATH}_{n}$ which is an infinite path with only one
endpoint. This object is then expanded to a Boolean-valued model of weak
second order arithmetic $K(*\text{PATH}_{n},F_{\text{nb}},G_{\text{nb}})$ in
which every instance of OntoWeakPigeon has a solution. However, the object
$\lim_{F_{\text{nb}}}*\text{PATH}_{n}$ in the model
$K(*\text{PATH}_{n},F_{\text{nb}},G_{\text{nb}})$ is an instance of the PPA-
complete problem Leaf that does not have a solution (Corollary 6.10). This can
be seen as a logical analogue of an oracle separation of these two classes,
which is known to hold555OntoWeakPigeon can be reduced to WeakPigeon which is
known to be in PPP[8], and it is known [1] that Leaf cannot be reduced to any
problem in PPP.. We then show the result implies a separation of those classes
under stronger notion of reducibility (Section 6.3). To prove this result we
essentially show that in a relativized world with an oracle access
$\mathcal{O}$ to an uniformly sampled random path on exponentially many
vertices we get that
$\textsc{Leaf}^{\mathcal{O}}\not\in\textbf{FP}^{\mathcal{O}}$ but
$\textsc{OntoWeakPigeon}^{\mathcal{O}}\in\textbf{FP}^{\mathcal{O}}$ with
probability $1$.

There is already an established connection between complexity of search
problems and logic (namely witnessing theorems in bounded arithmetic, see [5],
[13]). The model we construct is not known nor expected to be a model of any
theory which has been considered under these investigations. However, we show
that open induction and open comprehension is valid in this model, and thus we
show these principles along with the principle that OntoWeakPigeon is total
cannot prove that the problem Leaf is total. The way the model is constructed
also implies nonreducibility from Leaf to OntoWeakPigeon for subexponential
time oracle machines. Moreover, one can at least in theory tweak our
construction (e.g. by extending the family $F_{\text{nb}}$) to obtain a model
of a stronger theory, for example some fragement of bounded arithmetic theory
$V_{1}$. This has been successfully done for several models already in [10,
Chapter 10, Chapter 14, Chapter 21] using the switching lemma.

This work is organized in the following manner. In Section 2 we recall
preliminary notions, most importantly nonstandard models of arithmetic. In
Section 3 we give the definition of the wide limit, provide several examples
and show how density of finite substructures corresponds to validity of
existential sentences in the wide limit. Section 4 we start by recalling the
definition of total NP search problems. The rest of the section is then
dedicated to proving Theorem 4.10 which says that the wide limit of hard Leaf
instances $*\text{PATH}_{k}$, relative to shallow trees querying the neighbor
sets of vertices, is (elementarily equivalent) to a path with a beginning but
no end. In Section 5 we recall a definition of second order models of
arithmetic $K(F,G)$ from [10] and show that (under some reasonable
assumptions) every wide limit can be expanded to such a model in a way that
preserves valid first order sentences. Finally, in Section 6 we combine the
results from the previous two sections, to show that the wide limit of
$*\text{PATH}_{k}$ constructed earlier can be expanded to a model of (weak)
second order arithmetic, where the problem Leaf is not total while the problem
OntoWeakPigeon is. In Section 6.3 we show how this construction implies
nonreducibility of Leaf to OntoWeakPigeon and give a remark on how separations
of TFNP can be framed in our setting and how these separation rule out
existence of any reduction, which is guaranteed to work only on a constant
fraction of some hard instances.

##  2 Preliminaries

By graphs we mean structures in a language with a single binary relation
denoted $E$ which is antireflexive and possibly symmetric if the graph in
question is undirected. We will denote any particular graph by $\omega$ as it
will be used in some sense as a sample of a discrete probability space. The
edge relation of a particular graph $\omega$ will be denoted $E_{\omega}$.

In the rest of this section, we recall notions needed for Krajíček’s forcing
construction. A fundamental notion we use throughout the work is of
nonstandard models of (true) arithmetic. Let $L_{all}$ be the language
containing the names of all relations and functions on the natural numbers and
let $\text{Th}_{L_{all}}(\mathbb{N})$ denote the set of true sentences in this
language in the standard model $\mathbb{N}$. By classical results of logic
there exist $L_{all}$-structures in which all sentences from
$\text{Th}_{L_{all}}(\mathbb{N})$ are valid but which are not isomorphic to
$\mathbb{N}$. These are called _nonstandard models_ (of
$\text{Th}_{L_{all}}(\mathbb{N})$).

All nonstandard models of $\text{Th}_{L_{all}}(\mathbb{N})$ (and even much
weaker theories) contain an isomorphic copy of $\mathbb{N}$ as an initial
segment. Therefore, we can assume that in fact all models we encounter satisfy
$\mathbb{N}\subseteq\mathcal{M}$. After considering a concrete nonstandard
model $\mathcal{M}$ (of $\text{Th}_{L_{all}}(\mathbb{N})$) we shall call the
elements of $\mathcal{M}\setminus\mathbb{N}$ _nonstandard numbers_. These can
be intuitively understood as “infinite natural numbers”. The key feature of
those elements is that all functions and relations from $L_{all}$ are defined
even on nonstandard numbers. This includes functions for coding sequences and
sets by numbers, and therefore we can use notation like $a_{0},\dots,a_{n-1}$
even for a nonstandard number $n$. The notation then means that for each
$i\in\mathcal{M}$ such that $i<n$ we have an object $a_{i}$ coded by a number
in $\mathcal{M}$ and that this whole sequence is coded by some number
${\\{a_{i}\\}}_{i=0}^{n-1}\in\mathcal{M}$. For a nonstandard number
$S\in\mathcal{M}$ coding a set we denote its nonstandard size (cardinality) to
be $\lvert S\rvert$. In the case where we talk about a binary string $x$ the
notation $\lvert x\rvert$ denotes the bit length of $x$ (which is nonstandard
if $x$ is). The symbol $\infty$ in sequences $\\{a_{i}\\}_{i=0}^{\infty}$
implies indexing over standard natural numbers, and in limits
$\lim_{k\to\infty}(\dots)$ has the standard meaning.

In the next section we will fix a nonstandard model $\mathcal{M}$ which has
the model theoretic property of being $\aleph_{1}$-saturated. There is a self-
contained construction of such model in [10, Appendix]. The only consequence
of the $\aleph_{1}$-saturation we shall use is the following.

######  Property.

For any sequence ${\\{a_{i}\\}}_{i=0}^{\infty}$ of standard numbers, there is
$t\in\mathcal{M}\setminus\mathbb{N}$ and a sequence
${\\{b_{i}\\}}_{i=0}^{t}\in\mathcal{M}$ such that for all $i\in\mathbb{N}$ it
holds that $a_{i}=b_{i}$. We shall call such a sequence of
$\\{b_{i}\\}_{i=0}^{t}$ a _nonstandard prolongation of_
$\\{a_{i}\\}_{i=0}^{\infty}$.

The language $L_{all}$ contains symbols for all relations on $\mathbb{N}$.
Since every sequence of numbers can be defined by some relation it turns out
that in our case there is a unique nonstandard prolongation which matches the
definition of the wide sequence (up to length which can be chosen arbitrarily
high). We can therefore allow ourselves to use nonstandard numbers as indices
of any sequences of objects unambiguously.

Any nonstandard model $\mathcal{M}$ can be extended to an ordered ring
$\mathbb{Z}^{\mathcal{M}}$ by adding negative elements. This ring then can be
extended to a fraction field $\mathbb{Q}^{\mathcal{M}}$. We shall call
elements of $\mathbb{Q}^{\mathcal{M}}$ $\mathcal{M}$_-rationals_. The field
$\mathbb{Q}^{\mathcal{M}}$ contains an isomorphic copy of $\mathbb{Q}$ as a
substructure. We shall use the structure $\mathbb{Q}^{\mathcal{M}}$
analogously to how hyperreal numbers are used in nonstandard analysis. For
more details about nonstandard analysis we recommend [4] to the interested
reader. We call an element in $\mathbb{Q}^{\mathcal{M}}$ with absolute valued
greater than all $\frac{k}{1},k\in\mathbb{N}$, _infinite_ otherwise we call it
_finite_. We call elements in $\mathbb{Q}^{\mathcal{M}}$ with absolute value
smaller than all $\frac{1}{k},k\in\mathbb{N}$ _infinitesimal_. We will denote
the set of finite $\mathcal{M}$-rationals as $\mathbb{Q}^{\mathcal{M}}_{fin}$
and one can check it forms an ordered ring.

######  Lemma (The existence of a standard part).

There is a function $\text{st}:\mathbb{Q}^{\mathcal{M}}_{fin}\to\mathbb{R}$
assigning to each finite $\mathcal{M}$-rational a real number. st is a ring
homomorphism and the kernel of st is exactly the ideal of infinitesimal
numbers. When $q$ is a finite $\mathcal{M}$-rational we call $\text{st}(q)$
its _standard part_.

The following result characterizes convergence of sequences of rational
numbers using $\mathbb{Q}^{\mathcal{M}}$.

######  Theorem.

Let $\\{a_{i}\\}_{i=0}^{\infty}$ be a sequence of rational numbers and let
$r\in\mathbb{R}$. Then the following are equivalent.

  * •

$\lim_{i\to\infty}a_{i}=r$

  * •

For every $\\{b_{i}\\}_{i=0}^{t}$, $t\in\mathcal{M}\setminus\mathbb{N}$, which
is a nonstandard prolongation of $\\{a_{i}\\}_{i=0}^{\infty}$, there is an
nonstandard $s_{0}\leq t$, such that for every nonstandard $s\leq s_{0}$:
$\text{st}(a_{s})=r$.

It is important for forcing with random variables to consider discrete
probability spaces of nonstandard size. We shall always use the uniform
distribution on the samples, although this is not necessary for the general
construction. Thus, the probability of an event coded by an element
$A\in\mathcal{M}$ is then just the $\mathcal{M}$-rational number $\lvert
A\rvert/\lvert S\rvert$ where $S$ is the set of samples of such a space.

We conclude this section by restating classical inequalities used in this work
using the nonstandard approach.

######  Theorem (Bernoulli’s inequlity).

Let $y\in\mathcal{M}$, $x\in\mathbb{Q}^{\mathcal{M}}$ and $x\geq-1$, then

$(1+x)^{y}\geq 1+yx.$

######  Theorem (Exponential inequality).

Let $x\in\mathcal{M}\setminus\mathbb{N}$, then

$\text{st}\left(\left(1-\frac{1}{x}\right)^{x}\right)\leq e^{-1}.$

##  3 Wide Limits

We shall define a wide limit of every sequence of the following form.

######  Definition 3.1.

A sequence of sets of graphs $\\{\mathcal{G}_{k}\\}_{k=1}^{\infty}$ is called
_a wide sequence_ if the following holds:

  * •

Every graph $\omega\in\mathcal{G}_{k}$ has the vertex set $\\{0,\dots,k-1\\}$.

  * •

$\lim_{k\to\infty}\lvert\mathcal{G}_{k}\rvert=\infty$.

By abuse of notation we will simply talk about a wide sequence
$\mathcal{G}_{k}$ instead of $\\{\mathcal{G}_{k}\\}_{k=1}^{\infty}$. Since a
wide limit is a Boolean-valued graph, we need to construct a Boolean algebra
in which the truth evaluation of statements shall take place. For the
construction of the Boolean algebra we will closely follow [10, Chapter 1]
albeit with slight changes. Let us fix now, for the rest of this work, an
$\aleph_{1}$-saturated model of $\text{Th}_{L_{all}}(\mathbb{N})$ which we
will denote $\mathcal{M}$.

######  Definition 3.2.

Let $n\in\mathcal{M}$. We define

$\mathcal{A}_{n}=\\{A\subseteq\\{0,\dots,n-1\\};A\in\mathcal{M}\\},$

in words $\mathcal{A}_{n}$ is the set of subsets of $\\{0,\dots,n-1\\}$ coded
by an element in $\mathcal{M}$. This is a Boolean algebra and to each
$A\in\mathcal{A}_{n}$ we assign an $\mathcal{M}$-rational $\lvert A\rvert/n$
which we call its _counting measure_.

Even though $\mathcal{A}_{n}$ is a boolean algebra with a “measure” it is not
a $\sigma$-algebra. Indeed, $\mathcal{A}_{n}$ contains all singletons
$\\{k\\}$ for $k$ standard, but the countable union of those singletons, the
set of standard natural numbers $\mathbb{N}$, is not definable by overspill.
However, having infinite joins and meets at our disposal allows us to
interpret quantifiers in the Boolean-valued case, so we now want to ‘tweak’
this Boolean algebra.

######  Definition 3.3.

Let $\mathcal{I}$ be the ideal of $\mathcal{A}_{n}$ consisting of elements
with infinitesimal counting measure. We define
$\mathcal{B}_{n}=\mathcal{A}_{n}/\mathcal{I}$. Each element in
$\mathcal{B}_{n}$ is of the form $A/\mathcal{I}$, where $A\in\mathcal{A}_{n}$,
and we define $\mu(A/\mathcal{I})=\text{st}(\lvert A\rvert/n)$. We will denote
the maximal element of $\mathcal{B}_{n}$ by 1 and the minimal element by 0.

One can easily check that $\mu$ is well-defined since for all
$A\in\mathcal{I}$ it holds that $\text{st}(\lvert A\rvert/n)=0$. The measure
$\mu$ is called the Loeb measure. The following then holds.

######  Lemma 3.4 ([10, Lemma 1.2.1]).

$\mathcal{B}_{n}$ is a $\sigma$-algebra with a real valued measure $\mu$.
Moreover, $\mathcal{B}_{n}$ is a complete boolean algebra.

It is important to note that $\textbf{1}\in\mathcal{B}_{n}$ is the only
element of $\mathcal{B}_{n}$ with measure $\mu(\textbf{1})=1$ and similarly
$\textbf{0}\in\mathcal{B}_{n}$ is the only element with measure
$\mu(\textbf{0})=0$. Also, for $B,B^{\prime}\in\mathcal{B}_{n}$ the inequality
$B\leq B^{\prime}$ implies $\mu(B)\leq\mu(B^{\prime})$.

We now define precisely what we mean by the family of functions $F$ relative
to which we will be taking the wide limit. This is still a part of Krajíček’s
construction, we just modify it to make it compatible with our setup that
starts with a wide sequence.

For every $k\in\mathbb{N}$ the set $\mathcal{G}_{k}$ is finite and thus can be
coded by a number. Therefore, there is a nonstandard prolongation of this
sequence, and we can consider the set coded by the nonstandard number
$\mathcal{G}_{n}$, which matches the definition of the wide sequence in
$\mathcal{M}$.

######  Definition 3.5.

Let $\\{\mathcal{G}_{k}\\}_{k=1}^{\infty}$ be a wide sequence and let
$n\in\mathcal{M}\setminus\mathbb{N}$. We say that $F$ is _a family of random
variables on_ $\mathcal{G}_{n}$ if every $\alpha\in F$ is a function coded by
a number in $\mathcal{M}$ with domain $\mathcal{G}_{n}$ and taking values in
$\mathcal{M}$. We say $\alpha\in F$ is an $F$-vertex if for all
$\omega\in\mathcal{G}_{n}$ it holds that $\alpha(\omega)\in\\{0,\dots,n-1\\}$.
The set of all $F$-vertices is denoted $U(F)$.

If the wide sequence $\\{\mathcal{G}_{k}\\}_{k=1}^{\infty}$ and the number
$n\in\mathcal{M}\setminus\mathbb{N}$ is clear from context we just say $F$ is
a family of random variables. This is for now everything we need to recall
from [10], and we can proceed to define the central object of our work.

######  Definition 3.6 (The wide limit).

Let $\\{\mathcal{G}_{k}\\}_{k=1}^{\infty}$ be a wide sequence, let
$n\in\mathcal{M}\setminus\mathbb{N}$ and let $F$ be a family of random
variables on $\mathcal{G}_{n}$. We define _the wide limit_
$\lim_{F,n}\\{\mathcal{G}_{k}\\}_{k=1}^{\infty}$ as a $\mathcal{B}_{n}$-valued
structure in the language consisting of a single binary relation symbol
$\\{E\\}$ as follows. The universe of the wide limit is taken as the set of
all $F$-vertices. We now inductively define the truth values for all
$\\{E\\}$-sentences.

  * •

${[\\![}\alpha=\beta{]\\!]}=\\{\omega\in\mathcal{G}_{n};\alpha(\omega)=\beta(\omega)\\}/\mathcal{I}$

  * •

${[\\![}E(\alpha,\beta){]\\!]}=\\{\omega\in\mathcal{G}_{n};E_{\omega}(\alpha(\omega),\beta(\omega))\\}/\mathcal{I}$

  * •

${[\\![}-{]\\!]}$ commutes with $\lnot$, $\land$ and $\lor$

  * •

${[\\![}(\exists x)A(x){]\\!]}=\bigvee_{\alpha\in
U(F)}{[\\![}A(\alpha){]\\!]}$

  * •

${[\\![}(\forall x)A(x){]\\!]}=\bigwedge_{\alpha\in
U(F)}{[\\![}A(\alpha){]\\!]}$

By abuse of notation we will denote the wide limit
$\lim_{F,n}\\{\mathcal{G}_{k}\\}_{k=1}^{\infty}$ by $\lim_{F}\mathcal{G}_{n}$.
To stress in which Boolean-valued structure is the truth evaluation
${[\\![}-{]\\!]}$ taking place we will sometimes denote the evaluation
$\mathcal{C}_{1}{[\\![}-{]\\!]}$, $\mathcal{C}_{2}{[\\![}-{]\\!]}$ for
Boolean-valued structures $\mathcal{C}_{1}$ and $\mathcal{C}_{2}$
respectively. Furthermore, if
$\mathcal{C}_{1}{[\\![}\varphi{]\\!]}=\textbf{1}$ for some sentence $\varphi$
we say $\varphi$ is _valid_ in $\mathcal{C}_{1}$.

Note that since $\mathcal{G}_{n}$ can be recovered from $F$ as the domain of
its elements, the wide limit only depends on $F$, strictly speaking. We keep
$\mathcal{G}_{n}$ in the notation to cover the situation where we have a very
general family of functions (e.g. the family of polynomial functions
$F_{\text{PV}}$) which can be applied to every wide sequence. Thus, the
notation $\lim_{F}\mathcal{G}_{n}$ means that $F$ is restricted to those
functions which take elements of $\mathcal{G}_{n}$ as an input even when $F$
possibly contains other functions too.

The variability of the parameter $n$ may also seem unnecessary and indeed in
our applications it is the case, but generally there are examples of wide
sequences where $n$ directly affects the wide limit.

######  Example 3.7.

Let $F_{const}$ be the family of all constant functions with domain
$\mathcal{G}_{n}$ and range anywhere in $\mathcal{M}$. Let

$\mathcal{G}_{k}=\begin{cases}\\{(\\{0,\dots,k-1\\},E);\lvert
E\rvert=2,(0,1)\in E\\}&\text{$k$ even}\\\ \\{(\\{0,\dots,k-1\\},E);\lvert
E\rvert=1,(0,1)\not\in E\\}&\text{$k$ odd}\\\ \end{cases}$

then

$\lim_{F_{const}}\mathcal{G}_{n}{[\\![}E(0,1){]\\!]}=\begin{cases}\textbf{1}&\text{$n$
even}\\\ \textbf{0}&\text{$n$ odd.}\\\ \end{cases}$

###  3.1 Wide Limits for Shallow Decision Trees

Now we shall define the first nontrivial family of random variables relative
to which we shall take wide limits of several sequences. The functions in the
family will be computed by shallow decision trees. So the shape of the wide
limit reflects what can tree of depth ‘superlogarithmic’ in $n$ witness in the
wide sequence with probability arbitrarily close to $1$.

######  Definition 3.8.

Let $\mathcal{T}_{\text{rud}}$ be a family666The subscript ‘rud’ stands for
rudimentary. The name for the family is taken from [10]. of labeled rooted
binary trees in $\mathcal{M}$ of the following form. At each vertex the tree
is labeled by an element of $\\{0,\dots,n-1\\}\times\\{0,\dots,n-1\\}$ and the
two outgoing edges incident to it are labeled as $0$ and $1$ respectively. The
leaves are labeled by an element of $\mathcal{M}$. The depth of the tree is
bounded by a number of a form $n^{1/t}$ (rounded to the nearest element of
$\mathcal{M}$) for some $t\in\mathcal{M}\setminus\mathbb{N}$.

A _computation_ of a $T\in\mathcal{T}_{rud}$ on some
$\omega\in\mathcal{G}_{n}$ is defined as follows. Start at the root and
interpret each label $(i,j)$ of the vertex as a question whether the pair
$(i,j)$ is in the edge set $E_{\omega}$ and follow a path through $T$ reading
$1$ as a positive answer and $0$ as a negative answer. The label of the leaf
visited at the end of the path is the output of $T$ on $\omega$, denoted
$T(\omega)$.

We define $F_{\text{rud}}$ to be the set of all functions computed by a tree
$T\in\mathcal{T}_{\text{rud}}$.

The simplest wide sequence we shall consider is the following sequence of sets
of undirected graphs with exactly one edge.

######  Definition 3.9.

$\text{EDGE}_{k}=\\{(\\{0,\dots,k-1\\},E);\lvert E\rvert=1\\}$

Since any $\omega\in\text{EDGE}_{k}$ has only $1$ edge in all potential
$k\cdot(k-1)/2$ edges, it is not likely a shallow tree will find the edge.
This is the idea behind the proof of the following theorem.

######  Theorem 3.10.

$\lim_{F_{\text{rud}}}\text{EDGE}_{n}{[\\![}(\exists x)(\exists
y)E(x,y){]\\!]}=\textbf{0}$

###### Proof.

Let $\alpha,\beta\in U(F_{\text{rud}})$, we proceed by proving that

${[\\![}E(\alpha,\beta){]\\!]}=\textbf{0}$

which is enough to prove the theorem since

${[\\![}(\exists x)(\exists y)E(x,y){]\\!]}=\bigvee_{\alpha\in
U(F_{\text{rud}})}\bigvee_{\beta\in
U(F_{\text{rud}})}{[\\![}E(\alpha,\beta){]\\!]}=\bigvee_{\alpha\in
U(F_{\text{rud}})}\bigvee_{\beta\in U(F_{\text{rud}})}\textbf{0}=\textbf{0}.$

Let $\alpha$ and $\beta$ be computed by $T\in\mathcal{T}_{\text{rud}}$ and
$S\in\mathcal{T}_{\text{rud}}$ respectively. Let the depth of both $T$ and $S$
be at most $n^{1/t}$, where $t\in\mathcal{M}\setminus\mathbb{N}$. Walk down
$T$ from the root and always prolong the path along the edge labeled $0$. On
this path we have a set of at most $n^{1/t}$ different pairs of vertices and a
label of the leaf $l_{T}$.

We do the same for $S$, and we find another set of at most $n^{1/t}$ pairs of
vertices and a label of the leaf $l_{S}$. The labels $l_{S}$ and $l_{T}$ are
then combined to one last pair $(l_{S},l_{T})$. Now we just need to compute
the probability that none of these $2n^{1/t}+1$ pairs of vertices are in the
edge set $E_{\omega}$.

There are $\binom{n}{2}$ different graphs in $\text{EDGE}_{n}$ and at least
$\binom{n-4n^{1/t}-2}{2}$ graphs which fulfill our requirements, namely, those
graphs whose sole edge does is not incident with the vertices from the labels
of the trees $S$ and $T$. The probability is thus at least

$\displaystyle\frac{\binom{n-4n^{1/t}-2}{2}}{\binom{n}{2}}$
$\displaystyle=\frac{(n-4n^{1/t}-2)(n-4n^{1/t}-3)}{n(n-1)}$
$\displaystyle\geq\frac{(n-4n^{1/t}-3)^{2}}{n^{2}}$
$\displaystyle\geq\left(1-\frac{4n^{1/t}+3}{n}\right)^{2}$
$\displaystyle\geq\left(1-\frac{8n^{1/t}+6}{n}\right)$

after taking the standard part of the last line we get
$\text{st}(1-\frac{8n^{1/t}+6}{n})=1$. Therefore,
$\mu({[\\![}E(\alpha,\beta){]\\!]})=0$ and
${[\\![}E(\alpha,\beta){]\\!]}=\textbf{0}$. ∎

###  3.2 Sufficient conditions for validity of universal and existential
sentences

To analyze wide limits we need ideally to know the values of sentences which
describe properties whose complexity we are interested in. Generally this can
be hard, so in this section we prove sufficient conditions at least for the
validity of universal and existential sentences.

We will start with the simpler condition for the validity of universal
sentences. This is important also because we would like to know that a wide
limit of a wide sequence of graphs (i.e. antireflexive $\\{E\\}$-structures)
is also a graph and that a wide limit of a wide sequence of undirected graphs
(directed graphs with $E$ symmetric) is an undirected graph. All of these
properties are expressible as universal sentences.

######  Theorem 3.11.

Let $\mathcal{G}_{k}$ be a wide sequence and let $F$ be any family of random
variables. Let $\varphi(x_{0},\dots,x_{l-1})$ be an open $\\{E\\}$-formula and
assume that

$\lim_{k\to\infty}\Pr_{\omega\in\mathcal{G}_{k}}[\omega\models(\forall\overline{x})\varphi(\overline{x})]=1.$

Then
$\lim_{F}\mathcal{G}_{n}{[\\![}(\forall\overline{x})\varphi(\overline{x}){]\\!]}=\textbf{1}$.

###### Proof.

By induction in $\mathcal{M}$ we have that
$\text{st}(\Pr_{\omega\in\mathcal{G}_{n}}[\omega\models(\forall\overline{x})\varphi(x)])=1$.
Therefore, we have for every tuple of $F$-vertices $\overline{\alpha}$ that
${[\\![}\varphi(\overline{\alpha}){]\\!]}=\textbf{1}$. Now

$\displaystyle{[\\![}(\forall x)\varphi(x){]\\!]}$
$\displaystyle=\bigwedge_{\overline{\alpha}\in
U(F)^{l}}{[\\![}\varphi(\overline{\alpha}){]\\!]}$
$\displaystyle=\bigwedge_{\overline{\alpha}\in U(F)^{l}}\textbf{1}$
$\displaystyle=\textbf{1}.$

∎

######  Corollary 3.12.

Let $\mathcal{G}_{k}$ be a wide sequence and $F$ any family of random
variables.

  * •

If all $\omega\in\mathcal{G}_{k}$, $k\in\mathbb{N}$, are directed graphs
($\\{E\\}$-structures satisfying that $E$ is antireflexive) then
$\lim_{F}\mathcal{G}_{n}$ is a Boolean-valued $\\{E\\}$-structure in which the
antireflexivity of $E$ is valid (i.e. $\lim_{F}\mathcal{G}_{n}$ is a Boolean-
valued graph).

  * •

If all $\omega\in\mathcal{G}_{k}$, $k\in\mathbb{N}$, are undirected graphs
(directed graphs where $E$ is symmetric) then $\lim_{F}\mathcal{G}_{n}$ is an
$\\{E\\}$-structure in which both antireflexivity and symmetry of $E$ is
valid. (i.e. $\lim_{F}$ is a Boolean-valued undirected graph)

Now to give a sufficient condition for the validity of an existential sentence
$(\exists\overline{x})\varphi(\overline{x})$ we use the auxiliary value of
_density of $\varphi(x_{0},\dots,x_{l-1})$_ defined as the probability that a
random graph $\omega\in\mathcal{G}_{k}$ and a random tuple
$\overline{a}\in\\{0,\dots,k-1\\}^{l}$ satisfy
$\omega\models\varphi(\overline{a})$ and show that the limiting density gives
a lower bound for the measure of
${[\\![}(\exists\overline{x})\varphi(\overline{x}){]\\!]}$.

######  Theorem 3.13.

Let $\mathcal{G}_{k}$ be a wide sequence and let $F$ be a family of random
variables which contains all constant functions. Let
$\varphi(x_{0},\dots,x_{l-1})$ be an open $\\{E\\}$-formula and let
$p\in[0,1]$. Assume that

$\lim_{k\to\infty}\Pr_{\begin{subarray}{c}\omega\in\mathcal{G}_{k}\\\
\overline{a}\end{subarray}}[\omega\models\varphi(\overline{a})]\geq p,$

where $\overline{a}$ is sampled uniformly over all elements of
$\\{0,\dots,k-1\\}^{l}$. Then

$\mu(\lim_{F}\mathcal{G}_{n}{[\\![}(\exists\overline{x})\varphi(\overline{x}){]\\!]})\geq
p.$

In particular if $p=1$ then
$\lim_{F}\mathcal{G}_{n}{[\\![}(\exists\overline{x})\varphi(\overline{x}){]\\!]}=\textbf{1}.$

###### Proof.

Consider an array $C$ indexed by $\omega\in\mathcal{G}_{n}$ and
$\overline{a}\in\\{0,\dots,n-1\\}^{l}$ such that

$C_{\omega,\overline{a}}=\begin{cases}1&\omega\models\varphi(\overline{a})\\\
0&\text{otherwise.}\end{cases}$

By the assumption and induction in $\mathcal{M}$ we have that

$\text{st}\left(\frac{1}{n^{l}\lvert\mathcal{G}_{n}\rvert}\sum_{\omega\in\mathcal{G}_{n}}\sum_{\overline{a}}C_{\omega,\overline{a}}\right)\geq
p.$

We now claim that there exists a specific
$\overline{b}\in\\{0,\dots,n-1\\}^{l}$ such that
$\text{st}(\Pr_{\omega\in\mathcal{G}_{n}}[\omega\models\varphi(\overline{b})])\geq
p$. Assume for contradiction that the claim is false. Then

$\displaystyle\frac{1}{\lvert\mathcal{G}_{n}\rvert
n^{l}}\sum_{\omega\in\mathcal{G}_{n}}\sum_{\overline{a}}C_{\omega,\overline{\alpha}}$
$\displaystyle=\frac{1}{n^{l}}\sum_{\overline{a}}\Pr_{\omega\in\mathcal{G}_{n}}[\omega\models\varphi(\overline{a})]$
$\displaystyle\leq\Pr_{\omega\in\mathcal{G}_{n}}[\omega\models\varphi(\overline{a}_{0})],$

where we pick $\overline{a}_{0}$ such that it maximizes
$\Pr_{\omega\in\mathcal{G}_{n}}[\omega\models\varphi(\overline{a}_{0})]$. But
after taking the standard part of the inequality we obtain that

$\text{st}\left(\frac{1}{n^{l}\lvert\mathcal{G}_{n}\rvert}\sum_{\omega\in\mathcal{G}_{n}}\sum_{\overline{a}}C_{\omega,\overline{a}}\right)\leq\text{st}(\Pr_{\omega\in\mathcal{G}_{n}}[\omega\models\varphi(\overline{a}_{0})])<p.$

Which is a contradiction and so the claim is true. Let $\overline{\gamma}_{b}$
be a tuple of constant functions which is at every sample equal to
$\overline{b}$. We have

$\displaystyle{[\\![}(\exists\overline{x})\varphi(\overline{x}){]\\!]}$
$\displaystyle=\bigvee_{\overline{\alpha}\in
U(F)^{l}}{[\\![}\varphi(\overline{\alpha}){]\\!]}$
$\displaystyle\geq{[\\![}\varphi(\overline{\gamma}_{b}){]\\!]}$

and by taking $\mu$ of this inequality we finally obtain that
$\mu({[\\![}(\exists\overline{x})\varphi(\overline{x}){]\\!]})\geq p$. ∎

In the following example, we use Theorem 3.13 to show that in the wide limit
of graphs which have exactly one large clique and no other edges, the
nonexistence of a standard sized clique cannot be valid relative to any $F$
with all constants.

######  Example 3.14.

Consider the wide sequence

$\displaystyle\text{SK}_{k}^{1/2}$
$\displaystyle=\\{(\\{0,\dots,k-1\\},E);\text{$E$ has a clique of size
$\lfloor k/2\rfloor$ and no other edges}\\}.$

We will check that for an $\\{E\\}$-formula $\varphi_{l}(\overline{x})$ which
states that $\overline{x}$ forms a clique of size $l$ we have

$\lim_{k\to\infty}\Pr_{\begin{subarray}{c}\omega\in\text{SK}_{k}^{1/2}\\\
\overline{a}\end{subarray}}[\omega\models\varphi_{l}(\overline{a})]\geq(1/2)^{l}.$

Notice that we can compute the probability for a fixed $\overline{a}$ such
that $a_{i}\neq a_{j}$ whenever $i\neq j$, since the ratio of tuples
containing some vertex twice is infinitesimal. So we have

$\displaystyle\Pr_{\omega\in\text{SK}_{k}^{1/2}}[\omega\models\varphi_{l}(\overline{a})]$
$\displaystyle=\prod_{i=0}^{l-1}\left(1-\frac{k-\lfloor
k/2\rfloor}{k-i}\right)$ $\displaystyle\geq\left(1-\frac{k-\lfloor
k/2\rfloor}{k-l}\right)^{l}$
$\displaystyle\geq\left(1-\frac{1}{2(1-l/k)}-\frac{1}{k-l}\right)^{l}$

and since $l\in\mathbb{N}$ we just take the limit of the inner expression. But
one can see that $\lim_{k\to\infty}(1-l/k)=1$ and that
$\lim_{k\to\infty}(1/(k-l))=1$.

Now by Theorem 3.13 we obtain that for _any_ $F$ that contains all constants
we have

$\lim_{F}\text{SK}_{n}^{1/2}{[\\![}(\exists\overline{x})\varphi_{l}(\overline{x}){]\\!]}>\textbf{0}.$

The following example demonstrates that Theorem 3.11 cannot be generalized to
a similar hypothesis as Theorem 3.13.

######  Example 3.15.

Let $\mathcal{G}_{k}$ consist of all undirected graphs on the vertex set
$\\{0,\dots,k-1\\}$ with exactly $\lceil\frac{k(k-1)}{2\log(k)}\rceil$edges.
One can see that

$\lim_{k\to\infty}\Pr_{\begin{subarray}{c}\omega\in\mathcal{G}_{k}\\\
x,y\end{subarray}}[\omega\models\lnot E(x,y)]=1,$

but in fact $\lim_{F_{\text{rud}}}\mathcal{G}_{n}{[\\![}(\forall x)(\forall
y)\lnot E(x,y){]\\!]}=\textbf{0}$.

Let $t\in\mathcal{M}\setminus\mathbb{N}$ such that $n^{1/t}$ is not bounded
above by a standard number. Let $T$ be a tree which queries on all paths a
fixed set of $n^{1/t}$ different potential edges. If we prove that any such
set in $\mathcal{G}_{n}$ has to contain at least one edge with probability
infinitesimally close to $1$ then we can construct $F_{\text{rud}}$-vertices
$\alpha$ and $\beta$ using $T$ such that
${[\\![}E(\alpha,\beta){]\\!]}=\textbf{1}$ by simply taking $T$ and labeling
each leaf on a path which finds an edge with one of the vertices incident to
this edge.

Let $S$ be the set of potential edges queried by $T$ and let $m=\binom{n}{2}$.
Now we have

$\displaystyle\Pr_{\omega\in\mathcal{G}_{n}}[\text{$S$ contains no edge in
$\omega$}]$ $\displaystyle=\frac{(m-n^{1/t})!(m-\lceil\frac{m}{\log
n}\rceil!)}{m!(m-\lceil\frac{m}{\log m}\rceil-n^{1/t})!}$
$\displaystyle=\prod_{i=0}^{n^{1/t}-1}\frac{m-\lceil\frac{m}{\log
n}\rceil-i}{m-i}$ $\displaystyle\leq\left(1-\frac{\lceil\frac{m}{\log
n}\rceil}{m}\right)^{n^{1/t}}$ $\displaystyle\leq\left(1-\frac{1}{2\log
n}\right)^{n^{1/t}}$

standard part of which is for all $k\in\mathbb{N}$ bounded above by

$\displaystyle\text{st}\left(\left(1-\frac{1}{2\log n}\right)^{k\cdot 2\log
n}\right)$ $\displaystyle\leq e^{-k}$

which tends to $0$ as $k\to\infty$.

##  4 A Wide Limit of Leaf Instances

In this section we first recall the definition of total NP search problems,
particularly the problems Leaf and OntoWeakPigeon, whose (randomized) query
complexity we will analyze using wide limits in the rest of this work.

The class of total NP search problems TFNP, first defined in [12], consists of
all relations on binary strings $P(x,y)$ such that:

  * •

(_verifiability in polynomial time_) There is a polynomial time machine $M$
which, given $x,y$, can decide whether $P(x,y)$ holds.

  * •

(_totality_) There exists a polynomial $p$ and for every $x$ there exists at
least one $y$ satisfying $\lvert y\rvert\leq p(\lvert x\rvert)$ such that
$P(x,y)$ holds.

Two particular problems are relevant for us.

The problem Leaf is formulated as follows. An instance is given by a number
$k$ and a undirected graph $\omega$ on the vertex set $\\{0,\dots,2^{\lvert
k\rvert}-1\\}$, presented by a Boolean circuit of polynomial size in $\lvert
k\rvert$ computing its neighborhood function, such that $\deg_{\omega}(0)=1$
and $\forall v:\deg_{\omega}(v)\leq 2$. The task is then to find some nonzero
$v$ with $\deg_{\omega}(v)=1$. The corresponding combinatorial principle being
the handshaking lemma, which assures the problem is total.

The problem OntoWeakPigeon is formulated as follows. An instance is given by a
number $k$ and two functions $A:\\{0,\dots,2^{\lvert
k\rvert}-1\\}\to\\{0,\dots,2^{\lvert k\rvert-1}-1\\}$ and
$B:\\{0,\dots,2^{\lvert k\rvert-1}-1\\}\to\\{0,\dots,2^{\lvert k\rvert}-1\\}$,
each presented by a Boolean circuit of polynomial size in $\lvert k\rvert$.
The task is then to find some $x$ such that $B(A(x))\neq x$ or some $y$ such
that $A(B(y))\neq y$. The corresponding combinatorial principle being the
bijective weak pigeonhole principle, which assures the problem is total. The
domain of $A$ is twice as large as its range, so $B$ and $A$ cannot form a
pair of inverse functions between their respective domains.

So far, we presented what is called ‘type 1’ problem in [1]. We are interested
about the ‘type 2’ problems which replace the input function(s) with
oracle(s). So in the ‘type 2’ Leaf problem, the input is a pair $(\alpha,x)$
where $\alpha$ is an oracle which describes the neighbor function on $G$ with
vertex set $\\{0,\dots,2^{\lvert x\rvert}-1\\}$. For the ‘type 2’
OntoWeakPigeon problem, the input is a triple $(\alpha,\beta,x)$, where
$\alpha$ and $\beta$ are oracles describing the functions
$\alpha:\\{0,\dots,2^{\lvert x\rvert}-1\\}\to\\{0,\dots,2^{\lvert
x\rvert-1}-1\\}$ and $\beta:\\{0,\dots,2^{\lvert
x\rvert-1}-1\\}\to\\{0,\dots,2^{\lvert x\rvert}-1\\}$.

The associated computational models for the ‘type 1’ problems are Turing
machines and for the ‘type 2’ problems oracle Turing machines.

###  4.1 The wide limit and oracle trees

This whole section is dedicated to proving Theorem 4.10 which says that this
wide limit does not contain a solution even though all the graphs in the wide
sequence do. As a byproduct, we obtain a distribution of Leaf instances which
cannot be solved using polynomially large number of queries.

The wide sequence $*\text{PATH}_{k}$ (pointed paths on $k$ vertices) consists
of all undirected graphs $\omega$ on the vertex set $\\{0,1,\dots,k-1\\}$
which are isomorphic to a path with $k-1$ edges connecting all vertices and
$\deg_{\omega}(0)=1$. Graphs in $*\text{PATH}_{k}$ are ‘the hardest instances
of Leaf’ so we can expect the wide limit to reflect the complexity of these
instances relative to the family $F$ we choose.

Since each $\omega\in*\text{PATH}_{k}$ has only $k-1$ edges we can proceed
similarly to the proof of Theorem 3.10 to get the following (whether we search
among $n^{2}$ or $n$ potential edges does not affect the result of the
computation).

######  Lemma 4.1.

$\lim_{F_{\text{rud}}}*\text{PATH}_{n}{[\\![}(\exists x)(\exists
y)E(x,y){]\\!]}=\textbf{0}$

The more interesting family $F$ to consider is the family of functions
computed by query trees which on each node can ask what is the neighbor set of
each vertex in $\omega$, we can immediately see that such a family is able to
witness an existence of an edge. More importantly, such trees are used in the
analysis of type 2 TFNP problems as they can compute at least as much as
oracle computations of Turing machines (when we allow the depth of the trees
to be the same as the time of the oracle computations). Therefore, we will not
only obtain a non-trivial wide limit, but its (in)valid sentences will have
immediate consequences for existence of oracle computations.

######  Definition 4.2.

We define $\mathcal{T}_{\text{nb}}$ as the set of all labeled rooted trees of
the following shape:

  * •

Each non-leaf node is labeled by some $v\in\\{0,\dots,n-1\\}$.

  * •

For each $\\{u,w\\}\subseteq\\{0,\dots,n-1\\}$ and a node $v$ there is an
outgoing edge from $v$ labeled $\\{u,w\\}$ (it can be that $u=w$).

  * •

Each leaf is labeled by some $m\in\mathcal{M}$.

  * •

The depth of the tree is defined as the maximal number of edges in a path from
the root, and we require it is at most $n^{1/t}$ (rounded to the nearest
element of $\mathcal{M}$) for some $t\in\mathcal{M}\setminus\mathbb{N}$.

The _computation_ of such a tree in $\mathcal{T}_{\text{nb}}$ on
$\omega\in*\text{PATH}_{n}$ is defined as follows. We build a path by starting
at the root and interpreting every vertex labeled by some $v$ as a question
‘what are the neighbors of the vertex $v$?’ and we follow the output edge with
the answer and continue analogously until we find a leaf. The label of the
leaf is defined to be the output of the computation.

We define $F_{\text{nb}}$ to be the set of all functions on $*\text{PATH}_{n}$
which are computed by some $T\in\mathcal{T}_{\text{nb}}$.

Each tree computing some function in $F_{\text{nb}}$ can be thought of as a
protocol describing the behavior of a machine $M$ communicating with an oracle
describing a particular $\omega\in*\text{PATH}_{n}$. That is, the tree can
describe what kind of queries does the machine $M$ make to the oracle
describing $\omega$, depending on which queries have already been asked, and
how they were answered. In the study of total NP search problems presented by
oracles, we usually denote the size of the object by some $2^{\lvert x\rvert}$
where $x$ is an additional input to the problems. If $2^{\lvert x\rvert}=n$
then $n^{1/t}=2^{\lvert x\rvert/t}$ which for
$t\in\mathcal{M}\setminus\mathbb{N}$ corresponds to protocols describing
subexponential-time computations. If we prove that no tuple of
$F_{\text{nb}}$-vertices satisfies some open $\\{E\\}$-formula in
$\lim_{F_{\text{nb}}}*\text{PATH}$ we also prove that subexponential-time
oracle machines cannot solve the corresponding type 2 problem on at least a
constant fraction of the inputs. In the rest of this section we proceed to
prove that $\lim_{F_{\text{nb}}}*\text{PATH}_{n}$ has no vertex with degree
$1$ other than the vertex $0$.

To do so, we will consider computations of trees on samples with different
nonstandard lengths. For the rest of this section we put
$\mathcal{G}_{m}=*\text{PATH}_{m}$ for all $m\in\mathcal{M}$, but we can
assume $m$ to be smaller than $n$. We define $\mathcal{T}_{\text{nb}}^{(m)}$
to be the subset of $\mathcal{T}_{\text{nb}}$ consisting of all the trees that
have the vertex labels from $\\{0,\dots,m-1\\}$. For trees in
$\mathcal{T}_{\text{nb}}^{(m)}$ we can extend the definition of a computation
to input graphs from $\mathcal{G}_{m}$ in a straight forward way.

######  Definition 4.3.

We say a tree $T\in\mathcal{T}_{\text{nb}}^{(m)}$ _fails_ on
$\omega\in\mathcal{G}_{m}$ if the output of $T$ on $\omega$ has degree 2 or if
the output is $0$.

######  Definition 4.4.

Let $m\in\mathcal{M}$, $v\in\\{0,\dots,m-1\\}$ and
$\\{u,w\\}\subseteq\\{0,\dots,m-1\\}$, note that possibly $w=u$, we define

$\mathcal{G}_{m}^{v:\\{u,w\\}}=\\{\omega\in\mathcal{G}_{m};\omega\models
E(v,x)\iff x\in\\{u,w\\}\\}.$

The following lemma formalizes the observation, that after querying a neighbor
set of a single vertex $v$ in $\omega\in\mathcal{G}_{m}$ and contracting $v$
with its neighbors we essentially end up with a uniformly sampled path on
$\mathcal{G}_{m-1}$ or $\mathcal{G}_{m-2}$.

######  Lemma 4.5.

Let $m\in\mathcal{M}$ and let $u,v$ and $w$ be distinct elements of
$\\{1,\dots,m-1\\}$. Then there are bijections:

$\displaystyle\mathcal{G}_{m}^{v:\\{u,w\\}}$
$\displaystyle\cong\mathcal{G}_{m-2}\times\\{L,R\\}$
$\displaystyle\mathcal{G}_{m}^{v:\\{u,0\\}}$
$\displaystyle\cong\mathcal{G}_{m-2}$
$\displaystyle\mathcal{G}_{m}^{v:\\{u\\}}$
$\displaystyle\cong\mathcal{G}_{m-1}$
$\displaystyle\mathcal{G}_{m}^{0:\\{u\\}}$
$\displaystyle\cong\mathcal{G}_{m-1}$

###### Proof.

For the first case a bijection can be given as follows. Contract $u,v$ and $w$
to just one vertex $\min\\{u,v,w\\}$ and if $u$ is closer to $0$ than $w$
(along the path) pick $L$ otherwise pick $R$ and relabel the remaining
vertices using a function ‘new’ which has a property that if
$u^{\prime},v^{\prime}$ remain and $u^{\prime}<v^{\prime}$ as numbers then
$\text{new}(u^{\prime})<\text{new}(w^{\prime})$ and the range of new is
$\\{0,\dots,m-2\\}$. This can be inverted by first renaming the vertices using
$\text{new}^{-1}$ and then replacing $\min\\{u,v,w\\}$ by a path $(u,v,w)$
with the orientation given either by $L$ or $R$.

The second bijection is almost the same, but the orientation is clear since
$u$ is always the neighbor further from $0$ since the other neighbor is $0$.

The third and fourth bijections are given by just removing one end of the
graph and relabeling. ∎

We want to use the previous lemma to reduce the depth of any tree $T$ from
$\mathcal{T}_{\text{nb}}$ to obtain a lower bound on the probability that it
fails. We therefore now prove that a tree which computes on the graph obtained
by contracting and relabeling the same as it would on the original graph under
the condition that we know one of its neighbor sets.

######  Definition 4.6.

Let $m\in\mathcal{M}$ and $v\in\\{0,\dots,m-1\\}$. Let $u$ and $w$ be elements
of $\\{0,\dots,m-1\\}\setminus\\{v\\}$ and let
$T\in\mathcal{T}_{\text{nb}}^{(m)}$ be a tree with the root labeled $v$. By
$T_{v:\\{u,w\\}}$ we denote the induced subtree whose root is the vertex
neighboring the root of $T$ via the edge labeled $\\{u,w\\}$.

######  Lemma 4.7.

Let $m\in\mathcal{M}$. Let $T\in\mathcal{T}_{\text{nb}}^{(m)}$ be a tree with
the root labeled $v\neq 0$. For each $u$ and $w$ which are distinct elements
of $\\{0,\dots,m-1\\}\setminus\\{v\\}$ there exists a tree
$\tilde{T}_{v:\\{u,w\\}}\in\mathcal{T}_{\text{nb}}^{(m-2)}$ of the same depth
as $T_{v:\\{u,w\\}}$ such that

$\Pr_{\omega\in\mathcal{G}_{m}}[\text{$T_{v:\\{u,w\\}}$
fails}\mid\omega\models E(v,u)\land
E(v,w)]=\Pr_{\omega\in\mathcal{G}_{m-2}}[\text{$\tilde{T}_{v:\\{u,w\\}}$
fails}].$

If $T$ has the root labeled $0$ then there exists a tree
$\tilde{T}_{0:\\{u\\}}\in\mathcal{T}_{\text{nb}}^{(m-1)}$ of the same depth as
$T_{0:\\{u\\}}$ such that

$\Pr_{\omega\in\mathcal{G}_{m}}[\text{$T_{0:\\{u\\}}$ fails}\mid\omega\models
E(0,u)]=\Pr_{\omega\in\mathcal{G}_{m-1}}[\text{$\tilde{T}_{0:\\{u\\}}$
fails}].$

###### Proof.

In the case where the root is labeled by $v\in\\{1,\dots,m-1\\}$ we can
construct the tree $\tilde{T}_{v:\\{u,w\\}}$ by simply relabeling vertices of
$T_{v:\\{u,w\\}}$. We use the relabeling function ‘new’ from the proof of
Lemma 4.5. Now for every $\omega\in\mathcal{G}_{m}$ there is by the first
bijection in Lemma 4.5 a uniquely determined
$\omega^{\prime}\in\mathcal{G}_{m-2}$. The computation of
$\tilde{T}_{v:\\{u,w\\}}$ on $\omega^{\prime}$ is then of the same shape as
the computation of $T_{v:\\{u,w\\}}$ on $\omega$ assuming $\omega\models
E(v,u)\land E(v,w)$. And $\tilde{T}_{v:\\{u,w\\}}(\omega^{\prime})$ has the
same degree in $\omega^{\prime}$ as $T_{v:\\{u,w\\}}(\omega)$ does in
$\omega$.

The case where the root is labeled by $0$ is analogous, but we instead use the
relabeling from the fourth bijection in Lemma 4.5. ∎

The following combines the previous lemmas to give a lower bound on the
probability of $T\in\mathcal{T}_{\text{nb}}$ failing depending on its depth.

######  Lemma 4.8.

Let $T\in\mathcal{T}_{\text{nb}}^{(m)}$ of depth $d\in\mathcal{M}$ and let
$d\leq m$. Then we have

$\Pr_{\omega\in\mathcal{G}_{m}}[\text{$T$
fails}]\geq\prod_{i=0}^{d}\left(1-\frac{2}{m-2i-2}\right).$

###### Proof.

We proceed by induction on $d$. The case $d=0$ follows from

$\Pr_{\omega\in\mathcal{G}_{m}}[\text{$T$
fails}]\geq\left(1-\frac{1}{m-1}\right)\geq\left(1-\frac{2}{m-2}\right).$

Now for the inductive case we assume the lemma holds for $d-1$, and prove it
for $d$. If the root of $T$ is labeled $0$ we proceed as follows. For a given
$T$ let $u_{0}$ be the vertex which minimizes the value
$\Pr_{\omega\in\mathcal{G}_{m}}[\text{$T$ fails}\mid E(0,u_{0})]$ which exists
by the least number principle in $\mathcal{M}$. Then by Lemma 4.7 and the
induction hypothesis

$\displaystyle\Pr_{\omega\in\mathcal{G}_{m}}[\text{$T$ fails}]$
$\displaystyle\geq\Pr_{\omega\in\mathcal{G}_{m}}[\text{$T$ fails}\mid
E(0,u_{0})]$
$\displaystyle=\Pr_{\omega\in\mathcal{G}_{m-1}}[\text{$\tilde{T}_{0:\\{u_{0}\\}}$
fails}]$ $\displaystyle\geq\prod_{i=0}^{d-1}\left(1-\frac{2}{m-2i-3}\right)$
$\displaystyle\geq\prod_{i=0}^{d}\left(1-\frac{2}{m-2i-2}\right).$

Now for the case where the root of $T$ is labeled by nonzero $v$. First we
note that

$\displaystyle\Pr_{\omega\in\mathcal{G}_{m}}[\text{$v$ has degree $2\land\lnot
E(v,0)$}]=1-\frac{2}{m-1}.$

Now we choose distinct $u_{0},w_{0}$ such that they minimize

$\Pr_{\omega\in\mathcal{G}_{m}}[\text{$T_{v:\\{u_{0},w_{0}\\}}$ fails}\mid
E(v,u_{0})\land E(v,w_{0})].$

Then by the Lemma 4.7 and the induction hypothesis we have

$\displaystyle\Pr_{\omega\in\mathcal{G}_{m}}[\text{$T$ fails}]$
$\displaystyle\geq\left(1-\frac{2}{m-1}\right)\Pr_{\omega\in\mathcal{G}_{m}}[\text{$T_{v:\\{u_{0},w_{0}\\}}$
fails}\mid E(v,u_{0})\land E(v,w_{0})]$
$\displaystyle=\left(1-\frac{2}{m-1}\right)\Pr_{\omega\in\mathcal{G}_{m-2}}[\text{$\tilde{T}_{v:\\{u_{0},w_{0}\\}}$
fails}]$
$\displaystyle\geq\left(1-\frac{2}{m-1}\right)\prod_{i=0}^{d-1}\left(1-\frac{2}{m-2i-4}\right)$
$\displaystyle\geq\left(1-\frac{2}{m-1}\right)\prod_{i=1}^{d}\left(1-\frac{2}{m-2i-2}\right)$
$\displaystyle\geq\prod_{i=0}^{d}\left(1-\frac{2}{m-2i-2}\right).\qed$

Now we just need to observe that when $m=n^{1/t}$ the tree fails with
probability infinitesimally close to $1$.

######  Lemma 4.9.

Let $T\in\mathcal{T}_{\text{nb}}$, then
$\text{st}\left(\Pr_{\omega\in\mathcal{G}_{n}}[\text{$T$ fails}]\right)=1.$

###### Proof.

The depth of $T$ is bounded by $n^{1/t}$ for some
$t\in\mathcal{M}\setminus\mathbb{N}$. We have by Lemma 4.8 that

$\displaystyle\Pr_{\omega\in\mathcal{G}_{n}}[\text{$T$ fails}]$
$\displaystyle\geq\prod_{i=0}^{n^{1/t}}\left(1-\frac{2}{n-2i-2}\right)$ (1)
$\displaystyle\geq\left(1-\frac{2(n^{1/t}+1)}{n-2n^{1/t}-2}\right)$ (2)

and the standard part of this lower bound is $1$. ∎

Finally, in the next theorem we prove that a formalization of ‘there is a
nonzero vertex of degree $1$’ is not valid in
$\lim_{F_{\text{nb}}}*\text{PATH}_{n}$ and in fact its boolean value is 0.

######  Theorem 4.10.

$\lim_{F_{\text{nb}}}*\text{PATH}_{n}{[\\![}(\exists v)(\exists u)(\forall
w)(v\neq 0\land E(v,u)\land(E(v,w)\to w=u)){]\\!]}=\textbf{0}$

###### Proof.

By expanding the left-hand side of the statement we get

$\bigvee_{\alpha\in U(F_{\text{nb}})}\bigvee_{\beta\in
U(F_{\text{nb}})}\bigwedge_{\gamma\in U(F_{\text{nb}})}{[\\![}\alpha\neq
0\land E(\alpha,\beta)\land(E(\alpha,\gamma)\to\gamma=\beta){]\\!]}.$

Therefore, it is enough if we prove that for each $F_{\text{nb}}$-vertices
$\alpha$ and $\beta$ there exists an $F_{\text{nb}}$-vertex $\gamma$ such that

${[\\![}\alpha\neq 0\land
E(\alpha,\beta)\land(E(\alpha,\gamma)\to\gamma=\beta){]\\!]}=\textbf{0}.$

For any $\alpha,\beta\in U(F_{\text{nb}})$ we can append the tree computing
$\beta$ to every leaf of a tree computing $\alpha$. This is still a tree in
$\mathcal{T}_{\text{nb}}$ as its depth is at most twice the maximum of depths
of the original trees. Append two more queries to each path in this tree:
$\alpha(\omega)$ and $\beta(\omega)$ (concrete values of $\alpha(\omega)$ and
$\beta(\omega)$ are already decided at the end of each path, and for each path
may differ). It is clear that we can label the leaves of the resulting tree to
obtain a tree computing a function

$\gamma(\omega)=\begin{cases}v&\text{if $\deg_{\omega}(\alpha(\omega))=1$ and
$v$ is the only neighbor of $\alpha(\omega)$}\\\ w&\text{if
$\deg_{\omega}(\alpha(\omega))=2$, $w$ is a neighbor of $\alpha(\omega)$ and
$w\not=\beta(\omega)$.}\end{cases}$

This is obviously an $F_{\text{nb}}$-vertex. Let us assume for contradiction
that

${[\\![}\alpha\neq 0\land
E(\alpha,\beta)\land(E(\alpha,\gamma)\to\gamma=\beta){]\\!]}>\textbf{0}.$

By definition this gives us

$\displaystyle 0$
$\displaystyle<\text{st}\left(\Pr_{\omega\in\mathcal{G}_{n}}[\alpha(\omega)\neq
0\land
E_{\omega}(\alpha(\omega),\beta(\omega))\land(E(\alpha(\omega),\gamma(\omega))\to\gamma(\omega)=\beta(\omega))]\right)$
$\displaystyle\leq\text{st}\left(\Pr_{\omega\in\mathcal{G}_{n}}[\alpha(\omega)\neq
0\land\deg_{\omega}(\alpha(\omega))=1]\right),$

but this is in contradiction with Lemma 4.9. ∎

##  5 Expanding Wide Limits to Second Order Arithmetic

As a part of the proof of Theorem 4.10 we proved what can be reformulated as
the statement that oracle instances of Leaf are not in oracle time
$\mathcal{O}(2^{f(\lvert x\rvert)})$ with $f\in o(\lvert x\rvert/c)$ for every
$c\in\mathbb{N}$ even when we just require it to be correct on any
nondiminishing ratio of inputs as $\lvert x\rvert$ grows. In the next section
we proceed to compare strength of (type 2) NP search problems not only with
oracle FP but also with other NP search problems via relative consistency of
their totality and nontotality. To do this, we will show that the wide limit
can be assumed to exist in a model of second order arithmetic, and moreover
the valid sentences of the wide limit stay valid when reformulated in the
model.

###  5.1 The structures $K(F,G)$

We will now recall the construction of second order models of weak arithmetic
$K(F,G)$ defined in [10, Chapter 5]. We will take the liberty to define them
as an extension of the definition of a wide limit to obtain structures
$K(\mathcal{G}_{n},F,G)$ 777This notation is just making some parameters of
the construction explicit, the models constructed can be obtained by the
original method without first constructing the wide limit. Our contribution is
in observing that the truth values of first order sentences concerning the
wide limit is preserved between the wide limit and the structure
$K(\mathcal{G}_{n},F,G)$.. Under the right conditions, these result in a
structure in some sublanguage of $L_{all}$ with two sorts: numbers and bounded
sets of numbers which contains the wide limit as an object of the second sort.

######  Definition 5.1.

Let $L\subseteq L_{all}$. This determines a _language $L^{2}$_ which we get by
adding to $L$ second order variables $X,Y,\dots$ whose intended interpretation
are bounded sets and the equality symbol for second order variables (denoted
the same as the first order one). All second order variables are treated as
function symbols and can form terms with the first order terms as arguments.

We will also use the second order variables as relation symbols, and we define
the atomic formula $X(x_{0},\dots,x_{k-1})$ simply to be evaluated as the
formula $X(x_{0},\dots,x_{k-1})\neq 0$. Fix a number $n$, a wide sequence
$\mathcal{G}_{k}$ and a family of random variables $F$ on $\mathcal{G}_{n}$
which all together determine a wide limit $\lim_{F}\mathcal{G}_{n}$.

######  Definition 5.2.

We define $\mathcal{M}_{n}\subseteq\mathcal{M}$ to be the subset of
$\mathcal{M}$ consisting of all numbers bounded above by $2^{n^{1/t}}$ for
some $t\in\mathcal{M}\setminus\mathbb{N}$.

######  Definition 5.3.

We define $L_{n}\subseteq L_{all}$ to contain all relation symbols from
$L_{all}$ and all functions from $L_{all}$ for which their values on any
element of $\mathcal{M}_{n}$ is still in $\mathcal{M}_{n}$. We say $F$ is
$L_{n}$-closed if for every function symbol $f\in L_{n}$ of arity $k$ and
every $\alpha_{0},\dots,\alpha_{k-1}\in F$ we have that
$f(\alpha_{0},\dots,\alpha_{k-1})\in F$.

Note that $\mathcal{M}_{n}$ is then a substructure of the $L_{n}$-reduct of
$\mathcal{M}$.

######  Definition 5.4.

We say that $G$ is a _family of random functions_ (on $\mathcal{G}_{n}$) if
every $\Theta\in G$ assigns to each $\omega\in\mathcal{G}_{n}$ a function
$\Theta_{\omega}$ coded by an element in $\mathcal{M}_{n}$.

We say $G$ is $F$-compatible if for every $\alpha\in F,\Theta\in G$ we have
that the function $\Theta(\alpha)$ defined as

$\Theta(\alpha)(\omega)=\begin{cases}\Theta_{\omega}(\alpha(\omega))&\text{if
$\alpha(\omega)\in\text{dom}(\Theta_{\omega})$}\\\
0&\text{otherwise}\end{cases}$

is in fact in $F$.

######  Definition 5.5.

Let $F$ be an $L_{n}$-closed family of random variables with values in
$\mathcal{M}_{n}$. Let $G$ be an $F$-compatible family of random functions. We
define $K(\mathcal{G}_{n},F,G)$ to be a $\mathcal{B}_{n}$-valued $L_{n}^{2}$
structure with first order sort of the universe $F$ and second order sort of
the universe $G$. The valuation of formulas is then given by the following
inductive definition:

  * •

${[\\![}\alpha=\beta{]\\!]}=\\{\omega\in\mathcal{G}_{n};\alpha(\omega)=\beta(\omega)\\}/\mathcal{I}$,
where $\alpha,\beta\in F$

  * •

${[\\![}R(\alpha_{0},\dots,\alpha_{k-1}){]\\!]}=\\{\omega\in\mathcal{G}_{n};\omega\models
R(\alpha_{0}(\omega),\dots,\alpha_{k-1}(\omega))\\}/\mathcal{I}$, where
$\alpha_{0},\dots,\alpha_{k-1}$ are from $F$ and is $R$ a relation symbol in
$L_{n}$

  * •

${[\\![}\Theta=\Xi{]\\!]}=\\{\omega\in\mathcal{G}_{n};\Theta_{\omega}=\Xi_{\omega}\\}/\mathcal{I}$,
where $\Theta,\Xi\in G$

  * •

${[\\![}(\forall x)A(x){]\\!]}=\bigwedge_{\alpha\in F}{[\\![}A(\alpha){]\\!]}$

  * •

${[\\![}(\exists x)A(x){]\\!]}=\bigvee_{\alpha\in F}{[\\![}A(\alpha){]\\!]}$

  * •

${[\\![}(\forall X)A(X){]\\!]}=\bigwedge_{\Theta\in G}{[\\![}A(\Theta){]\\!]}$

  * •

${[\\![}(\exists X)A(X){]\\!]}=\bigvee_{\Theta\in G}{[\\![}A(\Theta){]\\!]}$.

###  5.2 Preservation of sentences concerning the wide limit

We will now prove (under a mild condition on $F$) that there is a second-order
object in $K(\mathcal{G}_{n},F,G)$ which faithfully encodes the wide limit
$\lim_{F}\mathcal{G}_{n}$. This lets us construct models in which an object
elementary equivalent to the wide limit might be desired.

######  Definition 5.6.

We say that the edge relation of the wide limit $\lim_{F}\mathcal{G}_{n}$ is
_represented in $G$ by $\Gamma$_ if $\Gamma\in G$ and for all $\alpha,\beta\in
U(F)$ we have that

$K(\mathcal{G}_{n},F,G){[\\![}\Gamma(\alpha,\beta){]\\!]}=\lim_{F}\mathcal{G}_{n}{[\\![}E(\alpha,\beta){]\\!]}.$

######  Definition 5.7.

We say a family of random variables $F$ has _restrictable ranges_ if for every
$\alpha\in F$ and $m\in\mathcal{M}_{n}$ there is $\tilde{\alpha}_{m}\in F$
such that

$\tilde{\alpha}_{m}(\omega)=\begin{cases}\alpha(\omega)&\alpha(\omega)<m\\\
0&\text{otherwise.}\end{cases}$

######  Theorem 5.8.

Let $\varphi$ be a $\\{E\\}$-sentence. Let $F$ be $L_{n}$-closed and have
restrictable ranges and let $G$ be $F$-compatible. Let the edge relation of
the wide limit $\lim_{F}\mathcal{G}_{n}$ be represented in $G$ by $\Gamma$. We
define $\tilde{\varphi}(\Gamma)$ to be the $L_{n}^{2}$-sentence obtained by
replacing all the occurrences of the relation symbol $E$ by $\Gamma$, keeping
the structure of the logical connectives and replacing all quantifiers
$(\forall x)(\dots)$ by $(\forall x)(x<n\to(\dots))$ and $(\exists x)(\dots)$
by $(\exists x)(x<n\land\dots)$.

Then we have that that

$\lim_{F}\mathcal{G}_{n}{[\\![}\varphi{]\\!]}=K(\mathcal{G}_{n},F,G){[\\![}\tilde{\varphi}(\Gamma){]\\!]}.$

###### Proof.

We will prove that for all $\\{E\\}$-formulas $\varphi(\overline{x})$ and all
$\overline{\alpha}\in U(F)$ we have that

$\lim_{F}\mathcal{G}_{n}{[\\![}\varphi(\overline{\alpha}){]\\!]}=K(\mathcal{G}_{n},F,G){[\\![}\tilde{\varphi}(\Gamma,\overline{\alpha}){]\\!]}.$

We proceed by induction on the complexity of the formula. The case for atomic
formulas is clear and the step for logical connectives also since
${[\\![}-{]\\!]}$ commutes with them. With the induction step for negation in
hand it is now enough to prove the inductive step for the universal
quantifier.

We assume that the statement holds for a formula of lower complexity
$\varphi(y,\overline{x})$. By the restrictability of ranges in $F$ we get that
for all $\beta\in F$ there is $\tilde{\beta}_{n}\in U(F)$ such that

$K(\mathcal{G}_{n},F,G){[\\![}\tilde{\varphi}(\Gamma,\tilde{\beta}_{n},\overline{\alpha}){]\\!]}\leq
K(\mathcal{G}_{n},F,G){[\\![}\beta<n\to\tilde{\varphi}(\Gamma,\beta,\overline{\alpha}){]\\!]}.$

Now we have that for all $\overline{\alpha}\in U(F)$

$\displaystyle K(\mathcal{G}_{n},F,G){[\\![}(\forall
y<n)\tilde{\varphi}(\Gamma,y,\overline{\alpha}){]\\!]}$
$\displaystyle=\bigwedge_{\beta\in
F}K(\mathcal{G}_{n},F,G){[\\![}\beta<n\to\tilde{\varphi}(\Gamma,\beta,\overline{\alpha}){]\\!]}$
$\displaystyle=\bigwedge_{\tilde{\beta}_{n}\in
U(F)}K(\mathcal{G}_{n},F,G){[\\![}\tilde{\varphi}(\Gamma,\tilde{\beta}_{n},\overline{\alpha}){]\\!]}$
(*) $\displaystyle=\bigwedge_{\tilde{\beta}_{n}\in
U(F)}\lim_{F}\mathcal{G}_{n}{[\\![}\varphi(\tilde{\beta}_{n},\overline{\alpha}){]\\!]}$
$\displaystyle=\lim_{F}\mathcal{G}_{n}{[\\![}(\forall
y)\varphi(y,\overline{\alpha}){]\\!]},$

where (*) follows from the inequality above and the fact that one can omit
truth values from conjunctions which are greater than other truth values. ∎

##  6 The model for separation of OntoWeakPigeon and Leaf

Now we are in a situation that lets us construct a model of weak second order
arithmetic that contains an instance of the problem Leaf without a solution.
Consider a suitable family $G_{\text{nb}}$ in which we can define not only the
wide limit itself but instances of some other search problem. We can then ask:
‘Do all these instances have a solution?’ This is a way to compare the
strength of the different total NP search problems by relative consistency
results. We will pick the family $G_{\text{nb}}$ such that validity of
totality of some search problem $P$ implies the nonexistence of a suitable
reduction from Leaf to $P$.

###  6.1 Failure of totality of Leaf

######  Definition 6.1.

Let $G_{\text{nb}}$ be the family of all random functions on
$*\text{PATH}_{n}$ such that for each $\Theta\in G_{\text{nb}}$ there exists a
tuple $(\gamma_{0},\dots,\gamma_{m-1})\in\mathcal{M}_{n}$ so that
$\gamma_{i}\in F_{\text{nb}}$ and for $\alpha\in F_{\text{nb}}$

$\Theta(\alpha)(\omega)=\begin{cases}\gamma_{\alpha(\omega)}(\omega)&\alpha(\omega)<m\\\
0&\text{otherwise.}\end{cases}$

In the models $\mathcal{M}_{n}$ we are working with there is a pairing
function $\langle i,j\rangle$ which can code pairs of numbers by a single
number thus we can represent functions of any finite arity by functions from
$G_{\text{nb}}$.

One can understand the tuples which compute the random functions from
$G_{\text{nb}}$ as tuples of protocols describing the computations of
subexponential oracle machines. Such a tuple defines a function which is at
every index of the tuple computed using queries to some
$\omega\in*\text{PATH}_{n}$. This allows us to conclude (Theorem 6.12) that
totality of OntoWeakPigeon in
$K(*\text{PATH}_{n},F_{\text{nb}},G_{\text{nb}})$ implies the nonexistence of
a many-one reduction from Leaf to $P$ as defined in [1].

######  Lemma 6.2.

  1. 1.

$F_{\text{nb}}$ has restrictable ranges

  2. 2.

$F_{\text{nb}}$ is $L_{n}$-closed

  3. 3.

$G_{\text{nb}}$ is $F_{\text{nb}}$-compatible

  4. 4.

the edge relation of $\lim_{F_{\text{nb}}}*\text{PATH}_{n}$ is represented in
$G_{\text{nb}}$.

###### Proof.

1, 2: Here we can proceed simply by relabeling the leaves of the trees
computing the functions from $F_{\text{nb}}$.

3: Assume that $\Theta\in G_{\text{nb}}$ is computed by a tuple
$(\gamma_{0},\dots,\gamma_{m-1})$. By induction in $\mathcal{M}$ there exists
$t\in\mathcal{M}\setminus\mathbb{N}$ such that $\forall i\in\\{0,\dots,m-1\\}$
the depth of $\gamma_{i}$ is at most $n^{1/t}$. Therefore, for all $\alpha\in
F_{\text{nb}}$ we have that $\Theta(\alpha)$ has also depth at most
$n^{1/t^{\prime}}$ for some $t^{\prime}\in\mathcal{M}\setminus\mathbb{N}$.
Thus, $G_{\text{nb}}$ is $F_{\text{nb}}$-compatible.

4: Let $\gamma_{\langle i,j\rangle}\in F_{\text{nb}}$ be computed by a tree in
$\mathcal{T}_{\text{nb}}$ which queries $i$ and outputs $1$ if the neighbor
set contains $j$ otherwise it outputs $0$. Let $\Gamma$ be computed by a tuple
$(\gamma_{\langle i,j\rangle})_{i,j=0}^{n-1}$. Then we have

$K(*\text{PATH}_{n},F_{\text{nb}},G_{\text{nb}}){[\\![}\Gamma(\alpha,\beta){]\\!]}=\lim_{F_{\text{nb}}}*\text{PATH}_{n}{[\\![}E(\alpha,\beta){]\\!]}.\qed$

In the following theorem we also state which additional principles hold in the
model. While we do not directly use these facts to get our nonreducibility
result, they can be understood as adding certain robustness to our model of
arithmetic.

######  Theorem 6.3.

Let $\varphi(x)$ be an open $L_{n}^{2}$-formula with parameters from
$F_{\text{nb}}$ and $G_{\text{nb}}$. Then for every $m\in\mathcal{M}_{n}$ the
open comprehension principle

$(\exists X)(\forall y<m)(X(y)\equiv\varphi(y))$

and the open induction principle

$\lnot\varphi(0)\lor\varphi(m)\lor(\exists
x<m)(\varphi(x)\land\lnot\varphi(x+1))$

are both valid in $K(*\text{PATH},F_{\text{nb}},G_{\text{nb}})$.

###### Proof.

This can be proven completely analogously to [10, Lemma 20.2.5]. ∎

######  Definition 6.4.

The $L_{n}^{2}$-formula $\varphi_{\text{{Leaf}}}(X,Y,m)$ is defined as the
disjunction of the following formulas

$\displaystyle(X(0)\neq Y(0)\lor X(0)=0)$ $\displaystyle(\exists
x)((x<m)\land(X(x)>m-1\lor Y(x)>m-1))$ $\displaystyle(\exists
x)((x<m)\land((X(x)=x\land Y(x)\neq x)\lor(X(x)\neq x\land Y(x)=x)))$
$\displaystyle(\exists x)((x<m)\land(Y(X(x))\neq x\land X(X(x))\neq
x)\lor(X(Y(x))\neq x\land Y(Y(x))\neq x)))$ $\displaystyle(\exists
x)((0<x<m)\land(X(x)=Y(x)\land X(x)\neq x)),$

this formula formalizes that if $X$ and $Y$ are functions representing the
neighbor set of each $x<m$ as $\\{X(x),Y(x)\\}\setminus\\{x\\}$ and $0$ has
only one neighbor then there has to exist another $y<m$ which also has only
one neighbor.

Finally, we prove the main result of this section concerning the non-totality
of leaf in $K(*\text{PATH},F_{\text{nb}},G_{\text{nb}})$.

######  Theorem 6.5.

$K(*\text{PATH}_{n},F_{\text{nb}},G_{\text{nb}}){[\\![}(\exists X)(\exists
Y)(\exists m)\lnot\varphi_{\text{{Leaf}}}(X,Y,m){]\\!]}=\textbf{1}$

###### Proof.

We can find $\Theta_{1},\Theta_{2}\in G_{\text{nb}}$ such that for each
$v\in\\{0,\dots,n-1\\}$ we have that
$\\{\Theta_{1}(v)(\omega),\Theta_{2}(v)(\omega)\\}$ is the neighbor set of $v$
on $\omega\in*\text{PATH}_{n}$. (We can just query $v$ and split the answer
between $\Theta_{1}$ and $\Theta_{2}$.)

By Theorem 4.10 we know that $\lim_{F}\mathcal{G}_{n}$ has one degree $1$
vertex and all other vertices of degree $2$ and by Lemma 6.2 we know that it
can be represented by some $\Gamma\in G_{\text{nb}}$. Furthermore, we can
verify that

${[\\![}(\Gamma(\alpha,\beta))\equiv(\Theta_{1}(\alpha)=\beta\lor\Theta_{2}(\alpha)=\beta){]\\!]}=\textbf{1},$

thus $\Theta_{1}$ and $\Theta_{2}$ do not satisfy the last disjunct of
$\varphi_{\text{{Leaf}}}$ otherwise it would be in contradiction with Theorem
4.10. By their construction and the definition of $*\text{PATH}_{k}$ we have
that $(\Theta_{1},\Theta_{2},n)$ does not satisfy the other disjuncts either.
∎

###  6.2 Totality of OntoWeakPigeon

The goal of this section is to show that the totality of OntoWeakPigeon is
valid in our constructed model. In subsection 6.3 we use this to obtain non-
reducibility of Leaf to OntoWeakPigeon.

######  Definition 6.6.

The $L_{n}^{2}$ formula $\varphi_{\text{{OntoWeakPigeon}}}(X,Y,m)$ is defined
as the disjunction of the following formulas

$\displaystyle(\exists x)((x<2m)\land(X(x)>m-1))$ $\displaystyle(\exists
y)((y<m)\land Y(y)>m-1))$ $\displaystyle(\exists x)((x<2m)\land Y(X(x))\neq
x)$ $\displaystyle(\exists y)((y<m)\land X(Y(y))\neq y)$

it formalizes the bijective weak pigeonhole principle which claims that any
pair of functions

$\displaystyle X:$ $\displaystyle\\{0,\dots,2m-1\\}\to\\{0,\dots,m-1\\}$
$\displaystyle Y:$ $\displaystyle\\{0,\dots,m-1\\}\to\\{0,\dots 2m-1\\}$

is not a pair of inverse bijections.

To prove that $\varphi_{\text{{OntoWeakPigeon}}}(X,Y,m)$ is valid in
$K(*\text{PATH}_{n},F_{\text{nb}},G_{\text{nb}})$ we will construct a tree
which finds some $x$ such that $Y_{\omega}(X_{\omega}(x))\neq x$ or
$X_{\omega}(x)>m-1$ with probability infinitesimally close to one. The
construction essentially goes as follows. At least half of the domain of $X$
is a solution to the problem, so we can find one element which is a solution
with probability at least $\frac{1}{2}$. If it happens that this element is
not the solution, we repeat the process and after nonstandardly many steps we
get the desired probability.

######  Definition 6.7.

Let $\Theta,\Xi\in G_{\text{nb}}$, and $\zeta\in F_{\text{nb}}$. We say that a
tree $T\in\mathcal{T}_{\text{nb}}$ _fails for_ $(\Theta,\Xi,\zeta)$ _on_
$\omega$ if

$\Theta_{\omega}(T(\omega))<\zeta(\omega)\text{\quad and
\quad}\Xi_{\omega}(\Theta_{\omega}(T(\omega)))=T(\omega).$

In words if $T$ does not witness the failure of $\Xi$ being the inverse
function to $\Theta$.

######  Lemma 6.8.

Let $\Theta,\Xi\in G_{\text{nb}}$ and $\zeta\in F_{\text{nb}}$. Then there is
a tree $T\in\mathcal{T}_{\text{nb}}$ such that

$\text{st}\left(\Pr_{\omega\in\mathcal{G}_{n}}[\text{$T$ fails for
$(\Theta,\Xi,\zeta)$}]\right)=0.$

###### Proof.

Let $\Theta$ be computed by $(\theta_{0},\dots,\theta_{2r-1})$ and $\Xi$ by
$(\xi_{0},\dots,\xi_{r-1})$, where $r$ is larger than any possible value of
$\zeta$.

We construct $T$ by stages and at each stage it will have some potential
output along each path. The initial stage $T_{0}$ will be the tree computing
$\zeta$ and from now on we will iteratively extend paths along this tree, thus
we can already assume that $\zeta$ will have some constant value $r^{\prime}$
(which depends on the path we extend). Now we notice that at each leaf $l$
there is at least one $i=i(l)\in\\{0,\dots,2r^{\prime}-1\\}$ such that the
probability that $\theta_{i}<r^{\prime}$ and $\xi_{\theta_{i}}=i$ is at most
$\frac{1}{2}$. We relabel each leaf $l$ of $T_{0}$ to the new label $i(l)$.

Assume $T_{d-1}$ have been constructed, we will describe how to extend
$T_{d-1}$ along each path $p$ to obtain $T_{d}$. If $T_{d-1}$ does not fail on
any $\omega$ compatible with $p$ we leave it as it is. Otherwise, let $i$ be
the label of the leaf on $p$. We can check whether $T$ fails (when outputting
$i$ on $\omega$ compatible with $p$) by first appending the tree $\theta_{i}$
to this path and then to each new leaf (labeled with a number $<r^{\prime}$)
appending $\xi_{\theta_{i}}$, and giving the leaves which confirm the
nonfailure of $T$ a new label $i$. Now consider a path $p^{\prime}$ extending
$p$ without determined output. We claim that there is
$j\in\\{0,\dots,2r^{\prime}-1\\}$ such that

$\Pr_{\mathcal{G}_{n}}[\theta_{j}<r^{\prime}\land\xi_{\theta_{j}}=j\mid\text{$p^{\prime}$
is compatible with $\omega$}]\leq\frac{1}{2},$

where $p^{\prime}$ being compatible with $\omega$ means that the computation
along $p^{\prime}$ agrees with the edge labels which would be chosen according
to $\omega$.

To prove the claim we notice that along $p^{\prime}$ it was confirmed that
already $d$-many distinct elements of $\\{0,\dots,2r^{\prime}-1\\}$ are in
bijection with some $d$-many elements of the set $\\{0,\dots,r^{\prime}-1\\}$.
Therefore, to fail further there are only at most $(r^{\prime}-d)$-many other
values $j^{\prime}$ in $\\{0,\dots,2r-1\\}$ for which it holds that
$\xi_{\theta_{j^{\prime}}}=j^{\prime}$. By an averaging argument (analogous to
the proof of Theorem 3.13) this is enough to show that at least for one of
them the claim holds since $\frac{r^{\prime}-d}{2r^{\prime}}\leq\frac{1}{2}$.
Thus, we let $j$ to be the label of the leaf of $p^{\prime}$ which concludes
the construction.

Therefore, by construction, for each $d\in\mathcal{M}_{n}$, $d<2r$ we have

$\displaystyle\Pr_{\omega\in\mathcal{G}_{n}}[\text{$T_{d}$ fails for
$(\Theta,\Xi,\zeta)$}]$ $\displaystyle\leq 2^{-d}.$

If $\zeta(\omega)\in\mathcal{M}_{n}\setminus\mathbb{N}$ on some $\omega$ then
we put $T=T_{t^{\prime}}$ for any nonstandard $t^{\prime}$ such that the depth
of $T$ is still bounded by some $n^{1/t}$, where
$t\in\mathcal{M}_{n}\setminus\mathbb{N}$. Otherwise, if $r^{\prime}$ is the
maximal value of $\zeta$, we put $T=T_{2r^{\prime}-1}$ and since this tree can
go through all the values in the effective domain of $\Theta$ it can never
fail. ∎

######  Theorem 6.9.

$K(*\text{PATH}_{n},F_{\text{nb}},G_{\text{nb}}){[\\![}(\forall X)(\forall
Y)(\forall m)\varphi_{\text{{OntoWeakPigeon}}}(X,Y,m){]\\!]}=\textbf{1}$

###### Proof.

By Lemma 6.8 we can construct for each $(\Theta,\Xi,\zeta)$ a tree
$T\in\mathcal{T}_{\text{nb}}$ which computes some function $\alpha$ which
validates the third disjunct of $\varphi_{\text{{OntoWeakPigeon}}}$. ∎

Compiling the results we have about
$K(*\text{PATH},F_{\text{nb}},G_{\text{nb}})$ we get the following.

######  Corollary 6.10.

In the structure $K(*\text{PATH},F_{\text{nb}},G_{\text{nb}})$ the following
are valid:

  * •

open induction with parameters from $F_{\text{nb}}$ and $G_{\text{nb}}$

  * •

open comprehension with parameters from $F_{\text{nb}}$ and $G_{\text{nb}}$

  * •

every instance of OntoWeakPigeon has a solution

  * •

there is an instance of Leaf which does _not_ have a solution.

###  6.3 Nonreducibility of Leaf to OntoWeakPigeon

In this section we recall the definition of reduction of type 2 TFNP problems
and then formally prove that no such reduction can exist from Leaf to
OntoWeakPigeon using the (non)totality of these problems in
$K(*\text{PATH}_{n},F_{\text{nb}},G_{\text{nb}})$. Let us assume a general
instance of a TFNP problem $P$ is a tuple $(\overline{\alpha},x)$, where
$\overline{\alpha}$ is a tuple of (standardly many) oracles.

######  Definition 6.11.

Let $P$ and $Q$ be type 2 TFNP problems, we say $P$ is _many-one reducible_ to
$Q$ if there are polynomial-time oracle functions $A$, $B$ and $C$ such that
for each instance $(\overline{\alpha},x)\in P$ we have that
$(\overline{\beta},y):=(B(\overline{\alpha},x,-),A(\overline{\alpha},x))$ is
an instance in $Q$ and for each solution $z$ to $(\overline{\beta},y)$ we have
that $C(\overline{\alpha},x,z)$ is a solution to $(\overline{\alpha},x)$.

######  Theorem 6.12.

Leaf is not many-one reducible to OntoWeakPigeon.

###### Proof.

Assume that there exist the functions $A$, $B$ and $C$ from the definition of
many-one reducibility. Then for each instance $\omega\in*\text{PATH}$ we
obtain a (nonstandard-sized) instance $(B(\omega,n,w),A(\omega,n))$ of
OntoWeakPigeon, since $A$ and $B$ are computed in oracle polynomial time, we
can compute them by tuples of trees from $\mathcal{T}_{\text{nb}}$ and thus
are in $G_{\text{nb}}$ as random functions. By Theorem 6.9 there is a tree
$\gamma\in\mathcal{T}_{\text{nb}}$ that finds a solution to this instance with
probability infinitesimally close to $1$.

However, since $C$ is also computable in oracle polynomial time, we obtain
that there is $\gamma^{\prime}\in\mathcal{T}_{\text{nb}}$ which finds a
solution to the instance $(\omega,n)$ which is represented in $G_{\text{nb}}$.
This is in contradiction with Theorem 6.5. ∎

It is possible, at least in theory, to compare the strength of any two classes
of oracle TFNP (whose instances can be presented as some relational
structures) by first picking complete problems $P$ and $Q$ for them, finding a
hard class of instances (in our case $*\text{PATH}$) for the one expected to
be harder, taking a wide limit of the distribution relative to the query trees
corresponding to the problem, and then showing the (harder) problem $P$ is not
total while the other problem $Q$ is actually total in the expanded model of
arithmetic. Notice, that the proof of Theorem 6.12 actually gives us more than
stated. The proof works verbatim to rule out the existence of any oracle
functions $A$, $B$ and $C$ which are a reduction only on some constant
fraction of the hard instances $*\text{PATH}_{n}$ and same would be true for
analogous separation of other TFNP classes.

##  7 Concluding remarks

We have to note that while the problem OntoWeakPigeon (and its variations)
have been investigated in the context of TFNP ($rWPHP$ in [6], ‘lossy code’ in
[9]), it has not been considered in the context of _oracle_ total NP search
problems and the proof of Theorem 6.9 cannot be adapted to prove that every
instance of the stronger WeakPigeon 888The problem to witness that
$\alpha:\\{0,\dots,2^{\lvert x\rvert}-1\\}\to\\{0,\dots,2^{\lvert
x\rvert-1}-1\\}$ is not injective. has a solution in
$K(*\text{PATH},F_{\text{nb}},G_{\text{nb}})$ because the presence of the
inverse function is essential to the construction of the witness.

A stronger problem called SourceOrSink is well established in the study of NP
search problems (it is the complete problem for PPAD, see [1]) and can be
formulated as follows: Given a directed graph $\omega$ on the vertex set
$\\{0,\dots,2^{\lvert x\rvert}-1\\}$ with the property that any vertex $v$ has
outdegree bounded by $1$ and indegree also bounded by $1$ and the indegree of
the zero vertex is $0$ find a nonzero vertex which is either a source or a
sink. In the type 2 setting the problem is given by a tuple
$(\alpha,\beta,x)$, where $x$ is a binary string and $\alpha$ and $\beta$
functions presented by an oracle with domain $\\{0,\dots,2^{\lvert
x\rvert}-1\\}$ computing the potential successor or predecessor of a given
vertex.

It was established in [1] that Leaf is not many-one reducible to SourceOrSink
and therefore this nonreducibility may be reflected in our model
$K(*\text{PATH},F_{\text{nb}},G_{\text{nb}})$. The way SourceOrSink is
presented is similar to how OntoWeakPigeon is presented (an analogous problem
called OntoPigeon was proved to be PPAD-complete in [2]), and thus a similar
strategy could be potentially used to solve the following problem.

######  Problem.

Let $\varphi_{\textsc{SourceOrSink}}(X,Y,m)$ be the formula formalizing that
$(X,Y,m)$ as an instance of SourceOrSink has a solution. Is it true that

$K(*\text{PATH},F_{\text{nb}},G_{\text{nb}}){[\\![}(\forall X)(\forall
Y)(\forall m)\varphi_{\textsc{SourceOrSink}}(X,Y,m){]\\!]}=\textbf{1}?$

## Acknowledgement

This work is based on the author’s master’s thesis [7] which was completed
under the supervision of Jan Krajíček. The author thanks Eitetsu Ken for
comments on a draft of this paper.

## References

  * [1] Paul Beame, Stephen Cook, Jeff Edmonds, Russell Impagliazzo, and Toniann Pitassi.  The relative complexity of np search problems.  In Proceedings of the Twenty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’95, page 303–314, New York, NY, USA, 1995. Association for Computing Machinery.
  * [2] Samuel R. Buss and Alan S. Johnson.  Propositional proofs and reductions between np search problems.  Annals of Pure and Applied Logic, 163(9):1163–1182, 2012.
  * [3] Ronald Fagin.  Probabilities on finite models.  The Journal of Symbolic Logic, 41(1):50–58, 1976.
  * [4] Isaac Goldbring.  Lecture notes on nonstandard analysis, 2014.  Available at https://www.math.uci.edu/~isaac/NSA%20notes.pdf (last accessed 9th of January 2023).
  * [5] J. Hanika.  Search problems and Bounded Arithmetic.  PhD thesis, Charles University, Prague, 2004.
  * [6] Emil Jeřábek.  Approximate counting by hashing in bounded arithmetic.  Journal of Symbolic Logic, 74(3):829–860, 2009.
  * [7] Ondřej Ježil.  Pseudofinite structures and limits.  Master’s thesis, Charles University, Prague, 2022.  Also available in Electronic Colloquium on Computational Complexity.
  * [8] Emil Jeřábek.  Integer factoring and modular square roots.  Journal of Computer and System Sciences, 82(2):380–394, 2016.
  * [9] Oliver Korten.  Efficient low-space simulations from the failure of the weak pigeonhole principle.  Electronic Colloquium on Computational Complexity, TR-22, 2022.
  * [10] Jan Krajíček.  Forcing with random variables and proof complexity, volume 382 of London Mathematical Society Lecture Note Series.  Cambridge University Press, 2011.
  * [11] László Lovász and Balázs Szegedy.  Limits of dense graph sequences.  Journal of Combinatorial Theory, Series B, 96(6):933–957, 2006.
  * [12] Nimrod Megiddo and Christos H Papadimitriou.  On total functions, existence theorems and computational complexity.  Theoretical Computer Science, 81(2):317–324, 1991.
  * [13] Moritz Müller.  Typical forcings, np search problems and an extension of a theorem of riis.  Annals of Pure and Applied Logic, 172(4):102930, 2021.
  * [14] Jaroslav Nešetřil and Patrice Ossona de Mendez.  A model theory approach to structural limits.  Commentationes Mathematicae Universitatis Carolinae, 53:581–603, 11 2012.
  * [15] Alexander A. Razborov.  Flag algebras.  The Journal of Symbolic Logic, 72(4):1239–1282, 2007.