The core argument in this paper it seems to me from scanning it is that because P != NP therefore LLMs will hallucinate answers to NP-complete problems.
I think this is a clever point and an interesting philosophical question (about math, computer science, and language), but I think people are mostly trying to apply this using our commonsense notions of "LLM hallucination" rather than the formal notion they use in this paper, and I don't see an obvious connection, since commonsense hallucinations (eg inventing chapters of a novel when asked to produce summaries, inventing specific details when asked) don't seem to be NP-complete problems but rather are hallucinatory for some other interesting reason. (I apologize if I have not captured the paper correctly and would welcome correction on that, I read it quickly)
The statement that the formal world (the world of math and logic and formal grammars) is a subset of the "real" world (or perhaps, the world of natural language) is really interesting to me as well. Most humans can't solve formal logic problems and parse formal grammars but don't suffer from a (strong) hallucination effect, and can work in natural language in great proficiency. Is hallucination inevitable in humans since we also can't solve certain NP-complete problems? We have finite lifespans, after all, so even with the capabilities we might never complete a certain problem.
I think this is a clever point and an interesting philosophical question (about math, computer science, and language), but I think people are mostly trying to apply this using our commonsense notions of "LLM hallucination" rather than the formal notion they use in this paper, and I don't see an obvious connection, since commonsense hallucinations (eg inventing chapters of a novel when asked to produce summaries, inventing specific details when asked) don't seem to be NP-complete problems but rather are hallucinatory for some other interesting reason. (I apologize if I have not captured the paper correctly and would welcome correction on that, I read it quickly)
The statement that the formal world (the world of math and logic and formal grammars) is a subset of the "real" world (or perhaps, the world of natural language) is really interesting to me as well. Most humans can't solve formal logic problems and parse formal grammars but don't suffer from a (strong) hallucination effect, and can work in natural language in great proficiency. Is hallucination inevitable in humans since we also can't solve certain NP-complete problems? We have finite lifespans, after all, so even with the capabilities we might never complete a certain problem.