Injective doesn’t mean bijective, and that seems obvious. That is, presumably very many inputs will map to the output “Yes”.
Afaict surjectivity was already a given before this paper, their contribution is the injectivity part (and thus invertibility)
Afaict surjectivity was already a given before this paper, their contribution is the injectivity part (and thus invertibility)