Un-differentiable output. Take, for instance, writing a program. Change the input by the smallest possible amount, one character, and generally the output changes by a rather large amount (it could, say, go from working to failing to compile). Rarely would changing one character get us X% closer to a solution, or produce a change in a working solution that is X% faster.

OTOH, the example in the OP has somewhat the flavor of the hard problem you just sketched.

The tree-based (RPN-esque) notation itself gets around much of the "perturbed program fails to compile" problem.

unique or novel untrained situations.

that said ,we're not great at those, either.

(untrained meaning that the dataset is a poor match with regards to the expected outcome)

employment