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.
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.