What makes verification potentially hard is the part where we have to quantify over all possible inputs—the verifier must work for any input.
I feel like it should be possible to somehow factor this discussion into two orthogonal claims, where one of the claims is something like “doing something for all inputs is harder than doing it for just one input” and the other is something like “it is harder to identify one particular example as noteworthy than it is to verify the noteworthiness of that particular example”.
And it seems likely to me that both claims are true if you separate them like that.
I feel like it should be possible to somehow factor this discussion into two orthogonal claims, where one of the claims is something like “doing something for all inputs is harder than doing it for just one input” and the other is something like “it is harder to identify one particular example as noteworthy than it is to verify the noteworthiness of that particular example”.
And it seems likely to me that both claims are true if you separate them like that.