What’s the threshold of special cases allowed where the problem is considered solved?

The second sentence in the comment you're replying to already answers your question.

If that is not good enough, I suspect that no possible answer would prove to be satisfactory.

“Almost” and “easily” are subjective and open to interpretation. My point is, that this is not a rigorous standard.

Languages are generally not very amenable to these things.

If you want to construct the entire field of linguistics mathematically that would certainly be interesting to watch. Since a function that is described by a simple equation is mathematically equivalent to a function that is described by a table assigning the appropriate values to each element of the function domain, you could try to come up with a definition for what constitutes the "optimal" way to describe a function. Do the same for any kind of relation.

Until you've done so linguists will sadly be stuck applying nothing more than common sense.

Just a few.

Buddy, I'm speaking English, it's full of exceptions.