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 think I might have an example! (even though it’s not 100% satisfying—there’s some logical inversions needed to fit the format. But I still think it fits the spirit of the question.)
It’s in the setting of polynomial identity testing: let F be a finite field and p(x) a polynomial over that field, and assume we have access to the representation of p (i.e. not just black-box access).
Two questions we can ask about p are:
EZE (Evaluates to Zero Everywhere): does p evaluate to zero on all inputs? That is, is it the case that ∀x,p(x)=0? Unfortunately, that’s coNP-hard.
PIT (Polynomial Identity Testing) -- decide if p is equal to the zero polynomial, that is, if all of p’s coefficients are 0. (Note that these are two distinct concepts: in the two-value field F2 we have x2−x=0 for all x, even though the polynomial is not zero). Polynomial identity testing can be done efficiently in probabilistic polynomial time.
Now, make f be the inverted Polynomial Identity Testing algorithm: f(p)=0 if p is zero, and 1 if it’s not zero. Then, assume our perspective is that EZE is the “fundamental” property. In that case f(p) can be 1 for two reasons: either the polynomial p doesn’t Evaluate to Zero Everywhere, or it’s one of those rare special cases mentioned above where it Evaluates to Zero Everywhere but isn’t identically zero. These to me seem like clearly distinct mechanisms. But to distinguish between them we need to check if p Evaluates to Zero Everywhere, and that’s co-NP hard, so an efficient discriminator (likely) doesn’t exist.
I think I might have an example! (even though it’s not 100% satisfying—there’s some logical inversions needed to fit the format. But I still think it fits the spirit of the question.)
It’s in the setting of polynomial identity testing: let F be a finite field and p(x) a polynomial over that field, and assume we have access to the representation of p (i.e. not just black-box access).
Two questions we can ask about p are:
EZE (Evaluates to Zero Everywhere): does p evaluate to zero on all inputs? That is, is it the case that ∀x,p(x)=0? Unfortunately, that’s coNP-hard.
PIT (Polynomial Identity Testing) -- decide if p is equal to the zero polynomial, that is, if all of p’s coefficients are 0. (Note that these are two distinct concepts: in the two-value field F2 we have x2−x=0 for all x, even though the polynomial is not zero). Polynomial identity testing can be done efficiently in probabilistic polynomial time.
Now, make f be the inverted Polynomial Identity Testing algorithm: f(p)=0 if p is zero, and 1 if it’s not zero. Then, assume our perspective is that EZE is the “fundamental” property. In that case f(p) can be 1 for two reasons: either the polynomial p doesn’t Evaluate to Zero Everywhere, or it’s one of those rare special cases mentioned above where it Evaluates to Zero Everywhere but isn’t identically zero. These to me seem like clearly distinct mechanisms. But to distinguish between them we need to check if p Evaluates to Zero Everywhere, and that’s co-NP hard, so an efficient discriminator (likely) doesn’t exist.