Re:Generating and solving difficult logic puzzles with LLMs
by brudgers on Saturday January 04, 2025 @02:17PM
(#42596947)
At first blush, this might be Job Shop Scheduling {1}. But I don't know {2}. If so, it is NP-Hard which means verifying an optimal solution is also in NP.
An LLM might be able to solve a toy scale problem with only four operations and lots of "machines." But I am skeptical it can solve problems of "interesting size" more effectively than numerical techniques because verification is also in NP. {3} Good luck.
An LLM might be able to solve a toy scale problem with only four operations and lots of "machines." But I am skeptical it can solve problems of "interesting size" more effectively than numerical techniques because verification is also in NP. {3} Good luck.
{1} https://en.wikipedia.org/wiki/Job_shop_scheduling
{2} "All shifts covered" seems like a requirement for optimality.
{3} Assuming the problem is Job Shop Scheduling.