A Knapsack by Any Other Name: Presentation impacts LLM performance on NP -hard problems (2025)

Abstract: To investigate the effect of problem presentation on LLMs’ ability to solve optimization problems, we introduce the dataset of Everyday Hard Optimization Problems (EHOP), a collection of NP-hard problems expressed in natural language. EHOP includes problem formulations that could be found in computer science textbooks (e.g., graph coloring), versions that are dressed up as problems that could arise in real life (e.g., party planning), and variants with inverted rules. We find that state-of-the-art LLMs, across multiple prompting strategies, systematically solve textbook problems more accurately than their real-life and inverted counterparts. While reasoning models are more capable, they nonetheless show high variance across problem presentations, suggesting they lack a truly robust reasoning mechanism. We argue that this constitutes evidence that LLMs are still heavily dependent on what was seen in training and struggle to generalize to novel problems.

## introduction many real world tasks that people face in their personal and professional lives are np hard opti mization problems. such problems are as diverse as planning family vacations, scheduling airline crews @xcite , and allocating organ donations @xcite . people rarely enjoy solving these problems, and they aren't particularly good at solving them either @xcite . one of the most exciting promises of large language models (llms) is that they can help non experts solve their real world computational prob lems when they express them in natural language (nl). the hope is that a wide range of users across a wide range of tasks will be able to describe their problem to an llm, and the llm will handle the difficult task of "problem solving," i.e., recogniz ing that the real world problem can be described textbook: given the undirected graph 𝐺, color its nodes such that no two adjacent nodes have the same color. use as few colors as possible. costumed (💔 parties with exes): your birth day is coming up, and you want to celebrate with all your friends. you do not want people who used to be in a relationship at the same party. how many parties do you need, and who should be invited to which party? inverted: given the undirected graph 𝐺, color its nodes such that no two non-adjacent nodes have the same color. use as few colors as pos sible. in terms of a known computational problem and then solving that problem efficiently and opti mally. in the case of np hard problems, this could potentially be accomplished either by the llm solving the problem by itself, e.g., through chain of thought (cot) reasoning @xcite , or by the llm converting the nl description into a linear program (lp) to be solved with specialized tools @xcite . however, recent work has raised the question of "reasoning vs. reciting": are llms actually car rying out systematic problem solving, or are they simply adapting solutions for similar problems in their training data @xcite ? llms that can only solve problems whose solution paths are documented on the internet will not fulfill the promise of opening robust, general problem solving to lay users. in this paper, we contribute to the reasoning vs. reciting debate by introducing the dataset of everyday hard optimization problems (ehop), which consists of np hard optimization problems presented in both textbook and real world variants (see figure 1 for an example). if llms perform reasoning, they should solve both variants at sim ilar levels of accuracy. if they recite, we would expect textbook problems, for which solution strategies are presented explicitly on the internet, to be easier. to enable this direct comparison, ehop introduces "costumes" for three well stud ied problems (graph coloring, knapsack, and traveling salesman) that represent real world situations with the same mathematical con straints. furthermore, we add inverted variants of all problems, which fundamentally distort the solutions of the problems with a small change in problem formulation. for standard llms, including gpt 4o (openai, 2024), llama 3.1 @xcite , and qwen3 32b @xcite we find that the proportion of textbook problems solved optimally is substantially higher than for the in verted and costumed variants, often by more than 20 percentage points. this holds across all three base problems, for different degrees of problem instance difficulty, and across multiple prompt ing strategies. the best performing approach uses llms to convert problems into lps and solves the lps with a separate tool, but the vulnerability to inversion and costuming persists. the only models we tested that do not ex hibit systematic performance degradations on our problem variants are deepseek r1 @xcite , which is specifically trained for reasoning and qwen3 32b in thinking mode. however, even these models display major fluctuations across variants and can underperform on costumes by over 20 percentage points in certain cases. thus, even on state of the art reasoning models, the pre sentation of the problem (textbook vs. costumed or inverted) greatly affects llm performance, suggesting that general, "reasoning" style problem solving with llms remains an open challenge. ## related work llms have been shown to perform remarkably well on benchmarks for complex problem solving tasks, such as tool use @xcite , complex gameplay @xcite , and planning @xcite . this has been attributed to the abil ity of iterative prompting strategies such as cot @xcite to perform general reasoning and problem solving. however, recent work has raised the question of whether llms actually perform systematic reasoning, or whether they are "reciting" solution paths from their training data and adapting them gracefully to the inference time problem @xcite . the fact that llm reasoners often degrade in accuracy for larger problem instances is one piece of evidence for the recitation hypothesis. furthermore, as long as chains of thought are limited to a polynomial num ber of steps, transformers provably solve exactly the problems that can be solved in polynomial time @xcite , failing to cover most reasoning problems, for which no optimal polynomial algorithms are known. in this paper, we focus on np hard optimization problems, with particular attention to the differ ence between textbook and everyday problems. previous work has investigated the ability of llms to solve np hard optimization problems (e.g. @xcite @xcite . here we do not aim to further improve llm based optimization as such; our focus is on the impact of problem presentation on llm performance. nonetheless, we include opro @xcite , one of the leading llm based optimizers, as a prompting strategy in the evaluation. finally, there are a number of existing datasets for evaluating models on np hard problems. nphardeval @xcite ) looks only at textbook problems, including the three base prob lems we consider here. grapharena @xcite evaluates llms on np hard graph problems with a variety of large real world graphs, and is also limited to textbook problems. nl4opt @xcite and nlp4lp @xcite provide evaluation datasets on real world np hard problems, but they are not linked to the underlying textbook problems. ehop differs from all these datasets in that we present the exact same instances of the base problem both in textbook and real world variants, making it possi ble for the first time to measure the impact of this distinction. ## everyday optimization problems an optimization problem is called np-hard if every problem that can be solved in non deter ministic polynomial time can be reduced to the problem in polynomial time @xcite . while it is generally assumed that deter ministic algorithms that solve np hard problems must have worst case exponential runtime, prob lems in np are still of lower computational complexity than, e.g., planning or reasoning. in 1 2 3 4 i have a network of 4 nodes, numbered 1 to 4, with various nodes being con nected to one another. i want to color the nodes such that no two connected nodes have the same color. the connections are as follows: node 1 and node 3 are connected. node 1 and node 4 are connected. node 2 and node 4 are connected. how can i color the nodes using the fewest colors possible? i am a teacher, and i want to assign my 4 students to different groups. i need the groups to focus, so i need to make sure that no two students who are friends with one another are in the same group, otherwise they may get distracted. i don't need the groups to all be the same size, but i want to minimize the total number of groups. the friendships are as follows: student 1 and student 3 are friends. student 1 and student 4 are friends. student 2 and student 4 are friends. which group should each student be assigned to? this paper, we focus on three well known np hard optimization problems (which we refer to as base problems): graph coloring, knap sack, and traveling salesman. to construct the dataset of everyday hard op timization problems (ehop), we first generate a number of random instances for each of the three base problems. instances are concrete examples of a problem; for example, an instance of the graph coloring problem consists of a specific graph 𝐺 (see figure 2 ). we present each instance in its textbook form, which uses terminology typical for the problem; in addition, we dress it up in three real world costumes and invert it. this yields a to tal of eight variants of each instance. appendix c shows examples of all variants. not all instances of an np hard problem are equally difficult. we therefore ensure that experi mental results remain comparable across variants, especially when we invert the problems. ## experiments we use ehop to measure the extent to which llms are vulnerable to changes in presentation when solving optimization problems. ## discussion the results above paint an intricate picture of the features that make it easy or difficult for an llm to solve np hard optimization problems. first, given previous research, it was expected that instance size would negatively impact accuracy. second, we have identified instance difficulty as an important factor: among instances of the same size, those that cannot be solved by greedy heuristics are also harder for llms. neurosymbolic methods that combine llms as semantic parsers with exact ilp solvers are more robust to both of these factors. as our main result, we established that the presentation of a problem instance impacts how difficult it is for llm based methods to solve. our "costumes" are quite transparent compared to the way we might expect a problem to be described by a lay user in real life. even so, all standard llms perform much worse on our costumed and inverted variants compared to the well established textbook presentations. this is true even when using advanced methods like opro. the story is a bit more nuanced for reasoning models, in which textbook sometimes outperforms the variants and is sometimes outperformed by them. however, given that textbook and the variants describe the exact same underlying optimization problem and the fact that the discrepancies persist even when the base problem is mentioned or recognized, our results are still evidence against a robust reasoning mechanism. furthermore, it is worth noting that deepseek r1 solves the everyday variants by recognizing the underlying textbook problem and then using strategies for solving this textbook problem. this is a valid strategy for the costumes in ehop, but many optimization problems that arise in real life-be it airline scheduling, allocating organ do nations, or travel planning-are not just dressed up versions of a single textbook problem. thus, strong performance on ehop does not ensure strong performance on real everyday problems. ## conclusion we have shown that the ability of an llm to solve np hard optimization problems is strongly affected by the presentation of the problem; there are reliable and large differences between the well documented textbook form and the everyday problems we developed for this paper. at least standard llms, such as gpt 4o, seem to often recite when they appear to be reasoning. one limitation of ehop as a dataset of real problem solving tasks is that real users will often not be able to spell out an instance of an everyday problem in detail, e.g. by assigning a numeric satis faction value to every museum in paris. it would be interesting to explore dialogue systems performing actual collaborative problem solving with the user. the costumes of ehop could be a good starting point for such work. acknowledgments. we gratefully acknowl edge fruitful conversations with peter clark and the members of the computational linguistics group at saarland university. this work was funded in part by the deutsche forschungsgemein schaft (dfg, german research foundation) -grk 2853/1 "neuroexplicit models of language, vision, and action" project number 471607914.