Tuesday 16 January 2024

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.

Tuesday 5 September 2023

Modeling and tuning genetic algorithms

Here is our latest work that presents a solution on the problem of Service Chain Embedding. It is based on genetic algorithms and extends a previously published conference paper.


The interesting contribution of this paper is a modeling framework for the operation of genetic algorithms. Using this framework we prove that NP-hard problems are not computed efficiently by genetic algorithms and we define some properties for the problems that genetic algorithms compute efficiently. 

Another interesting contribution of this paper is a performance optimization mechanism for genetic algorithms which is also based on genetic computing. So you use one genetic algorithm in order to optimize the performance of another.


Sunday 3 September 2023

Distributed Unsupervised Deep Learning

Our recently published paper, available here in open access mode, presents a deep learning method for network resource orchestration. There are a few features that make this method interesting.

It is build on a distributed multi-agent architecture.

It is based on Unsupervised Deep Learning, not a common feature for resource orchestration methods. The user essentially defines an objective and the agents try to accomplish it by training and then running deep neural networks and without further interaction with the user.

The agents share among them the most efficient models making the training process more efficient.

The neural networks are trained using genetic algorithms which is an innovative feature for unsupervised learning systems and speeds up the training procedure. It is actually interesting to use one system in order to train another system without explicitly describing the training process.

We are able to test this method by running simulations in large scale topologies. For this we have built an efficient network simulator resealed as an open source project.


https://doi.org/10.1109/ACCESS.2023.3308492




 

Wednesday 23 August 2023

An application for reading BIG files

There are many times that I want to read a big text file but current text viewers cannot handle it. 
So I decided to develop an application that would put me out of this trouble. 
It is open source and reseased in this repository

Wednesday 29 March 2023

On the Creative AI rush

It is weird how people react these days about Creative AI, especially ChatGPT. It was released a few months ago and many people already have developed an addiction on it while many others hate it or are afraid of it passionately.

How can serious professionals depend on a chat bot on their daily work? From my perspective they are either not serious or not professionals. Using such a great tool is reasonable but suddenly to depend on it out of the blue is  not rational. When the service stopped a few days ago some people were panicked. Really???

It is actually a great tool and has many programming potentials. The statement that these capabilities will some day signal the end of programming is not accurate. Trivial programming has passed away long ago. There are many tools and websites that actually help you build applications in seconds, it is not only chatGPT. But really innovative programming cannot be created by such chat bots that only use the knowledge that they have from their training and cannot, at least yet, create knowledge and science.

About the fear on the use of AI. Well, as any other technological achievement it can be used for the good or the bad, for the best or the worst of humanity. You can use a knife to cook or kill, on the same spirit you can use AI to detect and treat cancer or manipulate the elections.