>>13363152Problems that look complex and people solve through AI and metaheuristics are great candidates. If people are using metaheuristics or ML, chances are it's because they couldn't come up with a classical algorithm (like merge sort, Dijkstra, that kind of stuff) that was efficient and so the problem might be NP.
Metaheuristics are stuff like genetic algorithms, evolutionary algorithms in general (like ant colony optimization) and similar stuff.
Intelligent transport systems (optimizing the traffic lights and the routing of each vehicle) is that kind of problem where people just use AI to find approximate solutions. I wanted to optimize a public transportation system in my country and gave up when I learned that it was NP-complete and was called the Vehicle Routing Problem.
Predicting the structure of proteins would help us understand what they do, which would have big applications for our understanding of biology (and therefore medicine too), but it is NP-complete. DeepMind made progress with AI.
Predicting the properties of a material from its composition would be huge in material science but it probably is NP complete too.
I think that logic optimization is NP too. If you want to find the circuit with the least amount of logic gates that implements a logic function (like an adder), then you are screwed. Obviously very important in designing circuits. Google used AI to design a circuit:
https://ai.googleblog.com/2020/04/chip-design-with-deep-reinforcement.htmlThis is a list of applications of genetic algorithms. Chances are those problems are NP-complete and that's why they are being solved with genetic algorithms:
https://en.wikipedia.org/wiki/List_of_genetic_algorithm_applications 
