<p>(2.) implies (1.) by a standard compactness argument.</p>

<p>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$.</p>

<p>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$.</p>

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

CC BY-SA 3.0
2012-11-28T20:26:50.413Z
2012-11-28T20:26:50.413Z
Colin McQuillan
<p>A <em>search problem</em> is a relation $R\subseteq \Sigma^*\times\Sigma^*$. A function $f\colon \Sigma^*\to\Sigma^*$ <em>solves</em> $R$ if $(x,f(x))\in R$ for all $x\in\Sigma^*$. Define a search problem to be <em>reasonable</em> if for all $(x,y)\in R$ the word $x$ is at least as long as $y$.</p>

<p>Let $R$ and $S$ be reasonable search problems. Consider the following two properties.</p>

<ol>
<li>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".)</li>
<li>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$.)</li>
</ol>

<p>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.</p>

<cc.complexity-theory><reductions><function>
Cook reduction for search problems, by universal property?
Colin McQuillan
# Cook reduction for search problems, by universal property?

(Asked by: username_0 on 2012-11-23)

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.

**Tags:** cc.complexity-theory, reductions, function


---

## 1 answers

### Answer by username_0 on 2012-11-28. Score: 3 | Accepted answer

(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$.


---

