Alex Duchnowski

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

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 compute