Can you clarify what you mean by this, especially (i)?
In particular, right now I don’t have even a single example of a function f such that (i) there are two clearly distinct mechanisms that can lead to f(x) = 1, (ii) there is no known efficient discriminator for distinguishing those mechanisms. I would really love to have such examples.
In particular, do you mean f(x)=1 is true for all input x, or just some particular x, etc?
f(x) = 1 is true for a particular x. I’m imagining something like:
We have an f:{0,1}n→{0,1}, which we’re evaluating on random x∈{0,1}.
There’s a heuristic argument that P(f(x)=1)>0.1
This argument breaks into two parts: P(ϕ(x))=0.1 and ϕ(x)⇒f(x)=1.
There is no similarly-simple argument that cuts out the intermediate ϕ; it’s a “fundamental” part of the argument that f(x)=1 so often.
Yet there is no efficient way to test ϕ(x).
For example, I’m not aware of any way to argue that the Fermat test passes roughly 1logn of the time without first establishing that the density of primes is about 1logn, and so it seems reasonable to say that most of the time when it passes it is fundamentally “because of” the primality of n.
It means f(x) = 1 is true for some particular x’s, e.g., f(x_1) = 1 and f(x_2) = 1, there are distinct mechanisms for why f(x_1) = 1 compared to why f(x_2) = 1, and there’s no efficient discriminator that can take two instances f(x_1) = 1 and f(x_2) = 1 and tell you whether they are due to the same mechanism or not.
Can you clarify what you mean by this, especially (i)?
In particular, do you mean f(x)=1 is true for all input x, or just some particular x, etc?
f(x) = 1 is true for a particular x. I’m imagining something like:
We have an f:{0,1}n→{0,1}, which we’re evaluating on random x∈{0,1}.
There’s a heuristic argument that P(f(x)=1)>0.1
This argument breaks into two parts: P(ϕ(x))=0.1 and ϕ(x)⇒f(x)=1.
There is no similarly-simple argument that cuts out the intermediate ϕ; it’s a “fundamental” part of the argument that f(x)=1 so often.
Yet there is no efficient way to test ϕ(x).
For example, I’m not aware of any way to argue that the Fermat test passes roughly 1logn of the time without first establishing that the density of primes is about 1logn, and so it seems reasonable to say that most of the time when it passes it is fundamentally “because of” the primality of n.
I see, thank you! Will need time to digest this.
Yeah this was super unclear to me; I think it’s worth updating the OP.
It means f(x) = 1 is true for some particular x’s, e.g., f(x_1) = 1 and f(x_2) = 1, there are distinct mechanisms for why f(x_1) = 1 compared to why f(x_2) = 1, and there’s no efficient discriminator that can take two instances f(x_1) = 1 and f(x_2) = 1 and tell you whether they are due to the same mechanism or not.