Can we use AI to solve NP-Hard problems efficiently?

The growing research interest in Artificial Intelligence (AI) has led to the development of a plethora of methods and techniques that address difficult computational problems. The impressive progress on the field reasonably generates the question of whether we could use AI methods in order to solve efficiently traditionally hard problems or even to answer the NP vs P question.

These days the discussion on the possible relation of AI and NP-hardness revolves around two topics.

• Whether AI can resolve the NP vs P question
• If NP=P this will boost AI algorithms

On the first topic and at the time that this post is written, AI does not exhibit synthetic thinking so it is currently impossible to answer important problems as this. The second is really doubtful any way.

Let’s discuss a more practical aspect of the problem. AI methods deviate from traditional deterministic algorithms and in many cases overcome inherent obstacles of traditional computing. Then, could AI methods provide efficient solutions for NP-Hard problems?

There is huge literature on AI assisted approximation methods on NP-Hard problems that provide good and practical solutions for these problems sometimes achieving near optimal solutions for really hard instances of NP-Hard problems. So why not use them for actually solving them and provide exact solutions?

This reasonable question actually raises even more problems. Unlike traditional computing where Alan Turing solved the problem of modeling computation, AI methods lack general modeling of their operation. For some Machine Learning methods the researchers approach them experimentally and exhibit empirical evidences for their robustness without solid theoretical foundations.

The intense research in these issues gradually fills some of these gaps. In section 4 of our latest paper we provide a modeling framework for the operation of Genetic Algorithms (GA). Then we prove that GA may not solve efficiently classes of problems that include NP-Hard problems in every case; while they are pretty efficient on solving problems in P.

At least for now, it seems that AI can provide fast and practical approximate solutions for hard problems. But there is some pessimisms when we seek for exact solutions and confront NP-Hardness.