Comment by Sam Zhang (sam-zhang) on The subset parity learning problem: much more than you wanted to know · 2025-01-04T01:35:30.220Z · LW · GW

The analogue of $P\ne NP$ for randomized polynomial-time algorithms is actually $NP\ne RP$ (or equivalently $NP⊈BPP$), assuming that the intended meaning here is "$NP$-complete problems cannot be solved in polynomial time, even with randomized algorithms".^[1] More information about these classes are available here.

Also, a bit of a nitpick, but it looks like the claim that these widely-believed complexity-theoretic assumptions imply

that there is no way, in polynomial time, to get reliable information about A’s secret circuit C (beyond some statistical regularities) from looking at polynomially many input-output samples of C.

is implicitly claiming that a "learning problem" similar to the following is $NP$-hard:

There is a hidden function $f$ that takes $n$ bits as input and outputs one bit, and can be described with a polynomial-sized circuit. You are given some number of input-output pairs $(x_i,f(x_i\left)\right)$. Find a polynomial-sized circuit $C$ that is consistent with the given inputs and outputs.

It seems likely that this learning problem is indeed computationally difficult, given that the naive approach requires brute-force search through circuits. However, to actually prove $NP$-hardness, there needs to be a reduction from $3SAT$ (say) to that problem. I don't see any straightforward approach to construct such a reduction, even though it is not entirely implausible that one exists (possibly with minor modifications to the problem statement).

I do agree with the conclusion though that the problem being discussed here is very different from what is being captured by statements like $P\ne NP$.

1. ^{^}

   The statement $P\ne BPP$ actually means "randomized polynomial-time algorithms cannot be 'derandomized' by replacing them with equivalent deterministic polynomial-time algorithms".