Brcause LLMs are not “problem solving machines” they are text completion models, so (when trained for q-and-a response) their function is to produce text output which forms a plausible seeming response to the question posed, not to execute an algorithm which solves the logical problem it communicatss. Asking “why do LLMs do exactly what they are designed to do, even when they cannot do the thing that that behavior implies to a human would have been done to produce it” just reveals a poor understanding of what an LLM is. (Also, the fact that they structurally can't solve a class of problems does not mean that they can't produce correct answers, it means they can't infallibly produce correct answers; the absence of a polynomial time solution does not rule out an arbitrarily good polynomial time approximation algorithm, though its unlikely than an LLM is doing that, either.)