Funnily enough this very morning I asked an LLM to implement an algorithm for an NP-hard problem (a variation of the knapsack problem). I gave it 2 directives:

* Do not implement an np solution trying to get the perfect score. Implement a fast solution that gets within x% of optimal

* If a solution seems impossible or it takes too long, return the closes solution you can find, and a warning about the solution being suboptimal

I got the code in a few minutes. On a sample of random inputs, the algorithm produces a solution within 1% of optimal in ~99.9% of the cases. p95 execution time is well below 2ms in my laptop.

That's it, that's everything you need for a production system. "close enough" very fast is sufficient, and the impossible cases very rarely happen. Even when they do, you can simply work around them.