# Cook reduction for search problems, by universal property?

A search problem is a relation $R\subseteq \Sigma^*\times\Sigma^*$. A function $f\colon \Sigma^*\to\Sigma^*$ solves $R$ if $(x,f(x))\in R$ for all $x\in\Sigma^*$. Define a search problem to be reasonable if for all $(x,y)\in R$ the word $x$ is at least as long as $y$.

Let $R$ and $S$ be reasonable search problems. Consider the following two properties.

1. There is a Cook-reduction from $R$ to $S$ (That is, there is a polynomial-time oracle Turing machine $M$ such that for all $f$ solving $S$, the function $M^f$ solves $R$. This is Definition 3.1 of Goldreich's "P, NP, and NP-Completeness: The Basics of Computational Complexity".)
2. For all functions $f$ such that $S\in\mathsf{FP}^f$, we have $R\in\mathsf{FP}^f$. (Here $\mathsf{FP}^f$ is the set of search problems solved by $M^f$ for some polynomial-time oracle Turing machine $M$.)

Clearly (1.) implies (2.). Also, if $S$ solves itself (i.e. $S$ is a function) then (2.) implies (1.) because we can take the oracle in (2.) to be $S$ itself to obtain an appropriate $M$. Does (2.) imply (1.) in general? I'd guess the answer is no, but I can't think of a counterexample.

-

(2.) implies (1.) by a standard compactness argument.

First note that it suffices to exhibit a Cook-reduction $M$ from $R$ to $S'$ for any relation $S'$ such that $S(x,y)\iff S'(x,y)$ for all but finitely many values of $x$. This is because we can then give a Cook-reduction from $R$ to $S$ by simulating $S'$ using $S$.

Suppose for contradiction that there is no such Cook-reduction. Let $M_1,M_2,\dots$ be a enumeration of polynomial-time oracle Turing machines. Pick a sequence $S_1\supseteq S_2\supseteq \dots$ as follows. Let $S_1=S$. Suppose we have constructed $S_k$ such that $S_k(x,y)\iff S(x,y)$ for all but finitely many $x$. We know that $M_k$ is not a Cook-reduction from $R$ to $S_k$: there is some $f$ solving $S_k$ and some $x$ such that $R(x,M_k^f(x))$ does not hold. Set $S_{k+1}$ to be the relation that agrees with $f$ on all the oracle queries used by evaluating $M_k^f$ on $x$, and otherwise agrees with $S_k$.

Pick a function $f$ solving $S_k$ for all $k$. Clearing $S\in\mathsf{FP}^f$, but by construction $R\notin\mathsf{FP}^f$.

-