<p>This is a non-uniform (and simplified) version of my <a href="https://cstheory.stackexchange.com/questions/14450/cook-reduction-for-search-problems-by-universal-property">previous question about Cook reductions</a>. Let $R\subseteq \{0,1\}^*\times\{0,1\}$. A function $r\colon \{0,1\}^*\to\{0,1\}$ <em>solves</em> $R$ if $(x,r(x))\in R$ for all $x\in\{0,1\}^*$. Let $f\colon\{0,1\}^*\to\{0,1\}$. Consider the following two properties.</p>

<ol>
<li><p>There are polynomial-sized circuits using AND,OR,NOT and "$r$" gates, such that for all choices of function $r$ solving $R$, the circuits compute $f$.</p></li>
<li><p>For all choices of function $r$ solving $R$, there are polynomial-sized circuits that compute $f$, using AND,OR,NOT and $r$ gates.</p></li>
</ol>

<p>Does (2) imply (1)? A negative answer would mean that there's a problem $f$ that can be computed using any particular choices of $r(x)$, but cannot be computed efficiently if we do not fix particular choices of $r(x)$. The funny thing here is that the only obstacles are inputs $x$ with $(x,0),(x,1)\in R$. </p>

CC BY-SA 3.0
2012-12-03T21:01:04.380Z
Your "R"s are called promise problems. If f is a $P^{NP}$-complete problem, the resulting special case of your question is a circuit analog of Theorem 1 in Grollman and Selman: http://dx.doi.org/10.1137/0217018. I don't think this answers your question, since, as in your previous question, their proof uses the uniformity of Turing machines in an essential way, but it might provide some useful references/terminology to look up. Note that when they say a promise problem is "uniformly NP-hard" they mean in your sense (1.) (they're not using "uniform" to distinguish TMs from circuits).
Joshua Grochow
CC BY-SA 3.0
2012-12-05T07:39:20.210Z
Do we know anything about the case where $R$ is the whole space and each $r$ is thus an infinite bit-sequence? Apologies if this is well-known. I also wonder if this question might be related to BPP vs P somehow, as we might think of the indeterminate cases you mentioned as random bits and case (1) as a derandomization of some sort (though it's unclear how such an interpretation would go).
usul
CC BY-SA 3.0
2012-12-05T11:09:56.170Z
@usul: Yes! If we can take $r$ to be the all-zero sequence in (2.), then we can replace all the $r$ gates by $0$ gates (which I didn't add to my basis, but they can be removed quite easily), to get circuits for (1.).
Colin McQuillan
CC BY-SA 3.0
2012-12-05T16:49:07.350Z
Ah yes, excellent! So I think the same reasoning shows that (2) => (1) whenever there exists a solution to $R$ in P/poly? Hmm, cool.
usul
<circuit-complexity><advice-and-nonuniformity><function>
Can polynomial-sized circuits use garbage?
Colin McQuillan
# Can polynomial-sized circuits use garbage?

(Asked by: username_0 on 2012-12-03)

This is a non-uniform (and simplified) version of my [previous question about Cook reductions](https://cstheory.stackexchange.com/questions/14450/cook-reduction-for-search-problems-by-universal-property). Let $R\subseteq \{0,1\}^\*\times\{0,1\}$. A function $r\colon \{0,1\}^\*\to\{0,1\}$ *solves* $R$ if $(x,r(x))\in R$ for all $x\in\{0,1\}^\*$. Let $f\colon\{0,1\}^\*\to\{0,1\}$. Consider the following two properties.

1. There are polynomial-sized circuits using AND,OR,NOT and "$r$" gates, such that for all choices of function $r$ solving $R$, the circuits compute $f$.
2. For all choices of function $r$ solving $R$, there are polynomial-sized circuits that compute $f$, using AND,OR,NOT and $r$ gates.

Does (2) imply (1)? A negative answer would mean that there's a problem $f$ that can be computed using any particular choices of $r(x)$, but cannot be computed efficiently if we do not fix particular choices of $r(x)$. The funny thing here is that the only obstacles are inputs $x$ with $(x,0),(x,1)\in R$.

**Tags:** circuit-complexity, advice-and-nonuniformity, function

> **Comments:**
> **username_1**: Your "R"s are called promise problems. If f is a $P^{NP}$-complete problem, the resulting special case of your question is a circuit analog of Theorem 1 in Grollman and Selman: http://dx.doi.org/10.1137/0217018. I don't think this answers your question, since, as in your previous question, their proof uses the uniformity of Turing machines in an essential way, but it might provide some useful references/terminology to look up. Note that when they say a promise problem is "uniformly NP-hard" they mean in your sense (1.) (they're not using "uniform" to distinguish TMs from circuits).  
> **username_2**: Do we know anything about the case where $R$ is the whole space and each $r$ is thus an infinite bit-sequence? Apologies if this is well-known. I also wonder if this question might be related to BPP vs P somehow, as we might think of the indeterminate cases you mentioned as random bits and case (1) as a derandomization of some sort (though it's unclear how such an interpretation would go).  
> **username_0**: @username_2: Yes! If we can take $r$ to be the all-zero sequence in (2.), then we can replace all the $r$ gates by $0$ gates (which I didn't add to my basis, but they can be removed quite easily), to get circuits for (1.).  
> **username_2**: Ah yes, excellent! So I think the same reasoning shows that (2) => (1) whenever there exists a solution to $R$ in P/poly? Hmm, cool.  

---

## 0 answers

