Immagine to have a group of elements \$G\$, and a challenge that requires to output
truthy if the input is in \$G\$.
I suppose that in traditional programming hashing (Bloom filter?) is a good solution to this task.
But hashes have collisions, and since we are not so interested in avoiding them, one could come up with a dummy hash (or directly none), worst case scenario: all inputs yield
Of course, we could just ask to output
falsy if the input doesn't belong to \$G\$, but:
- Are there parameters that can be added in the rules in order to allow some margin of collision? (e.g. max false positive probability)
If so, would the challenge become too technical and infeasible to test?
- With absolute error free detection, how its complexity is related to the Kolmogorov complexity of \$G\$?
I see that it can be lower: check if input is a sudoku VS. output all possible sudoku...
Am I right?