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.