How Presentation Impacts LLM Performance on NP-Hard Problems | Insta After Hours

In this lecture, Alex Duchnowski, a software engineer at Instalily, presents research examining whether large language models can solve NP-hard problems robustly or whether their performance depends on how those problems are presented. Using graph coloring, knapsack, and traveling salesman problems, the talk introduces a novel dataset that varies problem framing through textbook descriptions, real-world contexts, and inverted constraints while preserving identical underlying structure. By comparing model performance across these equivalent formulations, the lecture explores the distinction between reasoning and recitation and discusses what these results imply for evaluating and trusting large language models on hard optimization problems.