/sci/ - Science & Math

I'm fighting with this question, I wonder if anyone finds it interesting or has any thoughts.

Let [math]\Upsilon[/math] be a finite set such that [math]\Upsilon \subset \N [/math]
We can write an algorithm [math]F(n)[/math] that either accepts n if [math]n \in \Upsilon[/math] or rejects otherwise. An algorithm that just checks on a big list with all the numbers of [math]\Upsilon[/math] is a fair algorithm, in the sense that it solves our problem, but it is not optimal in some cases. For example, [math]\Upsilon = {2,4,6,8,10}[/math] could be just checked by a simpler algorithm, that checks if the number is divisible by two and if it is less than 11. Although I did not prove it, we can agree that this is a good candidate for the optimal algorithm for checking such set, so we shall call it an optimal algorithm, because it is simpler than the naïve check. My question is, do all the sets [math]\Upsilon[/math] have an optimal algorithm?

>>9793164