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 truthy.
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?
| |
  • \$\begingroup\$ I don't really understand what the challenge you're thinking of writing would look like. Maybe write a short draft in the Sandbox? \$\endgroup\$ – xnor May 17 at 1:42
  • 1
    \$\begingroup\$ If there are a lot of possible valid input values, it's possible to use a randomized checker (possibly with a cryptographically secure random number generator to avoid cheating), and require that there's at least one seed such that there are >= x% of the tests are correct. \$\endgroup\$ – user202729 May 17 at 6:09
  • \$\begingroup\$ You can do what most similar challenges do: provide some truthy test cases and some falsy test cases (or perhaps many falsy test cases). If a solution passes all test cases, it's deemed good enough. However, Bloom filters are probably going to be fairly bad for this in [code-golf], because they require multiple hash functions and are not built-in in any languages I know about. \$\endgroup\$ – the default. May 17 at 15:55
  • \$\begingroup\$ @xnor Yes, I'll write it in the Sandbox before posting in main page. \$\endgroup\$ – Domenico Modica May 17 at 19:42
  • \$\begingroup\$ @user202729 I like that solution a lot because won't be trivial to locate the minima. \$\endgroup\$ – Domenico Modica May 17 at 19:42
  • \$\begingroup\$ @my pronoun is monicareinstate in term of simplicity that would be the best, but to find a good set of test cases is harder than setting a threshold and would also distract from the primary group \$\endgroup\$ – Domenico Modica May 17 at 19:43
  • \$\begingroup\$ @xnor I've opted for a strict identification. Can I tag it (not because of the fixed output part) as kolmogorov-complexity? Albeit the strings in question are not printed out, so it's not a classical kolmogorov-complexity challenge, I think that the involved techniques will be very similar. Also it seems like the "natural" other side of the coin of K.C., that is, the minimum length to accept one specific input. (My challenge it's already a complexification of this) Anyway I didn't find any challenge in this terms. What do you think? \$\endgroup\$ – Domenico Modica May 22 at 16:44

You must log in to answer this question.

Browse other questions tagged .