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.
