Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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: 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 Dec 3 '12 at 21:01
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 Dec 5 '12 at 7:39
@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 Dec 5 '12 at 11:09
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 Dec 5 '12 at 16:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.