[AdieuToLogic]

> Is there any theoretical reason why an attention based llm could or couldn't generate an answer to an NP hard problem?

Putting aside for the moment that a Large Language Model (LLM) is a predictive statistical model based on and producing from what consisted its training set, answering whether or not any algorithm can solve an NP hard problem first requires a clarification; is a brute force exhaustive search allowed?

If it is, I am unsure if an arbitrary LLM could find a solution due to the dependence on training. If not, I am confident in saying an LLM could not solve arbitrary NP hard problems in P time as that has yet to be proven possible AFAIK.

[epylar]

LLM's aren't statistical in the sense of memorizing percentages of words that come after other words. They are modeling a very high dimensional function using a neural net. I suppose they're statistical in the sense of learning how to mimic what they've seen, but this includes some very surprising emergent abilities as well.

[AdieuToLogic]

> LLM's aren't statistical in the sense of memorizing percentages of words that come after other words.

Agreed, in that LLM's are an improvement beyond Bayesian models[0].

> I suppose they're statistical in the sense of learning how to mimic what they've seen, but this includes some very surprising emergent abilities as well.

Your point of "mimic what they've seen" is what I mean by being predictive statistical models. And yes, there very well can be surprising, even emergent, output given depending on the training data set.

But to refocus back onto the original question the article presents, which is could an LLM somehow produce solutions to a problem category which has no solution with mathematical underpinning, is a bit fantastical IMHO.

0 - https://en.wikipedia.org/wiki/Bayesian_statistics