3
$\begingroup$

Just had this random idea... but unfortunately I'm not quite versed in complexity theory, so I thought it would be a good idea to ask it here.

Let's equip a normal Turing machine with a "black box oracle" that contains a boolean circuit of unknown size, and call this Turing machine a "black box machine". The black box oracle pretty much works the same way as an ordinary oracle machine, whose input and output (which are just the input/output of the circuit) are both polynomially bounded by the input size of our black box machine. As in the usual oracle machine's case, the evaluation of the black box circuit takes $O(1)$ time.

Now we define the boolean black box (BBB) problem:

(BBB) Given a circuit $C$ which size is polynomially bounded by $n$ and a black box $B$ which input and output are both polynomially bounded by $n$, determine whether $C$ will always behave identically as $B$ (in other words, for any possible input, whether $C$ and $B$ always produce the same result).

And the corresponding function problem:

(BBB-F) Given a black box $B$ which input and output are both polynomially bounded by $n$, compute a circuit $C$ that always behaves identically as $B$.

It seems to me that BBB is unlikely to be in $P$, or even $NP$, because generally one needs to check all $2^n$ possible input/output pairs, which would take more than polynomial time. However, what happens if we restrict the size of the black-box circuit to be polynomially bounded by $n$? (Notice that this does change something: if we restrict the size to be some constant $c$, then the problem can be solved in linear time. But what happens when the bound is polynomial?) Of course, we would also like to know if BBB-F will fall into $FP/FNP$ with this restriction.

A variant of this problem is that we only require the machine to be correct with a probability that is significantly higher than $1/2$. In other words, does $BBB \in PP$?

Third question: $PSPACE$. Can this possibly be solved in polynomial space?

Also, I can see some vague connections between this problem and some craptographic problems. For instance, I would guess that a CCA2-secure cryptosystem exists if and only if BBB-F is not in FP. To see the left-to-right part, simply put the decrypting procedure along with the secret key into a black box. An attacker with access to this black box has essentially the power to perform CCA2 attack. Now if BBB-F is indeed in FP, then we can construct a valid circuit $C$ within polynomial time that behaves the same as the black box circuit, which is the decryptor, and that would break the security of the system. As for the other way around, I don't have a good idea yet.

I googled quite a bit but couldn't find useful info about work done along this direction, so I would really appreciate it if someone can point me to some relevant literature. Any further thoughts on this problem would also be much appreciated. Thanks for your time!

$\endgroup$
  • 3
    $\begingroup$ This looks like a "learning boolean function" problem. $\endgroup$ – M. Alaggan May 16 '12 at 1:52
  • $\begingroup$ Yep seems like exactly what I'm looking for. Thanks! I guess I'll have to read a bit first to see if there are existing answers to my questions, although it'd be nice if someone happens to know some results and can point them out to me...:) $\endgroup$ – Charles Fu May 16 '12 at 2:10
  • $\begingroup$ Actually, the problems BBB and BBB-F above are not currently specified as a language or decision problem (the black box is not represented as a binary string of some kind, is it?), so they cannot be in NP or PSPACE. $\endgroup$ – Ryan Williams May 17 '12 at 5:28
7
$\begingroup$

Actually, the problems BBB and BBB-F above are not currently specified as languages or decision problems (the black box is not explicitly given to us as a binary string of some kind, is it?), so these problem cannot be in NP, PP, PSPACE, or even decidable/undecidable. A fundamental property of languages in the computability/complexity sense is that no bit of the initial input is "hidden" from you.

As suggested by M. Alaggan, the problems BBB and BBB-F are probably closest to the "learning with membership queries" framework, where one can only access a target function by querying it at various points and tries to infer the function. Nevertheless, both problems require superpolynomially many queries to the black box in the worst case, so they are both "intractable" in that sense. For BBB and BBB-F, your intuition is correct: it requires $\Omega(2^n)$ queries just to check that $B$ is not the "all-zeroes" function.

Even if you assume that the black box in these problems can be indeed modeled by some polynomial size circuit, it is highly unlikely that this helps. For example, if pseudorandom functions exist (a common cryptographic assumption) then for all $n$ there are polynomial size circuits $C_n$ with $n$ bits of input that cannot be distinguished from a completely random $n$-bit function, by any probabilistic subexponential time algorithm with black-box access to $C_n$. It follows that no subexponential time algorithm can efficiently reconstruct $C_n$ just from queries to $C_n$.

$\endgroup$
  • $\begingroup$ Thanks a lot for the detailed explanation! One additional thought: would it work if we restrict the size of the circuit to be logarithmically bounded? if so, would log-bounded be the "lower bound" condition? $\endgroup$ – Charles Fu May 17 '12 at 20:07
2
$\begingroup$

Googling "learning boolean function problem" from M. Alaggan says that BBB and BBB-F is at most NP-Hard and you can optimize the problem for certain inputs.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.