8
$\begingroup$

This is a non-uniform (and simplified) version of my previous question about Cook reductions. 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$.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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: 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). $\endgroup$
    – Joshua Grochow
    Dec 3, 2012 at 21:01
  • $\begingroup$ 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). $\endgroup$
    – usul
    Dec 5, 2012 at 7:39
  • $\begingroup$ @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.). $\endgroup$
    – Colin McQuillan
    Dec 5, 2012 at 11:09
  • $\begingroup$ 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. $\endgroup$
    – usul
    Dec 5, 2012 at 16:49

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy