Thank you for the nit, of course you’re correct about the NP analogue of BPP. I’ll edit.
And also thanks for operationalizing the generalized circuit “inversion problem” that’s analogous to the parity game described. This is exactly what I meant, but you put it better than I could have.
I think that if you restrict your class of circuits C to have some special form (i.e., “choose your architecture”) and also choose some specific collection of test inputs x_1, .., x_N, then you can make the code of C to depend on a secret boolean string, and have C(x_1), .., C(x_N) to return specific SAT instances of this boolean string; so a sufficiently “fiddly” version of this circuit reconstruction problem is equivalent to P vs. NP. However I think you’re right that hardness of the most natural version (in particular, where the inputs x_i are chosen at random) is probably closer to the existence of one-way functions than to P vs. NP.
Confirming that efficiently finding a small circuit (you don’t actually need further restrictions than size) based on its values on a fixed collection of test inputs is known to implyNP⊆BPP --- see this paper.
Thank you for the nit, of course you’re correct about the NP analogue of BPP. I’ll edit.
And also thanks for operationalizing the generalized circuit “inversion problem” that’s analogous to the parity game described. This is exactly what I meant, but you put it better than I could have.
I think that if you restrict your class of circuits C to have some special form (i.e., “choose your architecture”) and also choose some specific collection of test inputs x_1, .., x_N, then you can make the code of C to depend on a secret boolean string, and have C(x_1), .., C(x_N) to return specific SAT instances of this boolean string; so a sufficiently “fiddly” version of this circuit reconstruction problem is equivalent to P vs. NP. However I think you’re right that hardness of the most natural version (in particular, where the inputs x_i are chosen at random) is probably closer to the existence of one-way functions than to P vs. NP.
Confirming that efficiently finding a small circuit (you don’t actually need further restrictions than size) based on its values on a fixed collection of test inputs is known to imply NP⊆BPP --- see this paper.