It is not the case that "the search space is just the training data", the search space in NNs are some variants of real multivariate functions. The training data can be all manner of things, in LLMs, they are text in natural language. Graphs or natural language text are mapped from a discrete space to a continuous metric space.

It is true that LLMs cannot currently solve complex mathematics problems reliably. Whether that's an intrinsic shortcoming of transformers, or not is an interesting open question, that is being investigated as we speak. A lot of well-known DL research teams bet on transformers beating humans in mathematics in the next few years, see e.g.

   https://imo-grand-challenge.github.io/