Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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|improve this question
2  
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). –  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
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.